ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#185195 | #2022. a | snow_trace | 100 | 261ms | 3392kb | C++11 | 1.8kb | 2023-09-24 11:27:44 | 2023-09-24 12:03:56 |
answer
#include<bits/stdc++.h>
using namespace std;
int n;
int a[200005],b[200005];
vector<pair<int,int> >q;
void merge_sort(int l,int r){
//cout << l << " " << r << endl;
if(l >= r)return;
if(l+1 == r){
if(b[l+1] == 0 and b[l] == 1)swap(a[l],a[r]),swap(b[l],b[r]),q.push_back({l,l+1});
return;
}int mid = l+r>>1;
merge_sort(l,mid),merge_sort(mid+1,r);
int pos1,pos3 = r+1;
//cout << l << " " << r << endl;
// for(int i = l;i<=mid;i++)cout << b[i] << " ";cout << endl;
// for(int i = mid+1;i<=r;i++)cout << b[i] << " ";cout << endl;
if(b[mid] == 0 or b[mid+1] == 1)return;
for(int i = l;i<=mid;i++){
if(b[i] == 1){
pos1 = i;break;
}
}for(int i = mid+1;i<=r;i++){
if(b[i] == 1){
pos3 = i;break;
}
}pos3--;
q.push_back({pos1,pos3});
// cout << pos1 <<" " << pos3 << endl;
reverse(a+pos1,a+pos3+1),reverse(b+pos1,b+pos3+1);
}
void solve(int l,int r,int d){
if(d == -1)return;
if(l>=r)return;
// cout << l <<" " << r << endl;
for(int i = l;i<=r;i++)b[i] = a[i]>>d&1;
merge_sort(l,r);
// for(int i = l;i<=r;i++)cout << b[i] <<" ";cout << endl;
int pos =r+1;
for(int i = l;i<=r;i++){
if(b[i] == 1){
pos = i;break;
}
}solve(l,pos-1,d-1),solve(pos,r,d-1);
}
signed main(){
int mx =0;srand(time(0));
cin >> n;
for(int i = 1;i<=n;i++)cin >> a[i];
//n = 32000;
//for(int i = 1;i<=n;i++)a[i] = rand()%32000;
for(int i = 1;i<=n;i++)mx = max(mx,a[i]);
int pro = 1,cnt =-1;
while(pro<=mx)pro*=2,cnt++;pro/=2;
solve(1,n,cnt);
cout << q.size() << '\n';
for(int i = 0;i<q.size();i++)cout << q[i].first <<" " << q[i].second << '\n';
int sum = 0;
for(int i =0;i<q.size();i++)sum+=q[i].second-q[i].first+1;
// cout << sum << endl;
// for(int i = 1;i<=n;i++)cout << a[i] << " ";cout << endl;
return 0;
}
Details
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 20
Accepted
Test #1:
score: 20
Accepted
time: 0ms
memory: 1256kb
input:
63 19732 30594 10113 7702 9784 6421 4697 13517 5317 8508 26509 15653 2986 31587 11246 12158 24378 49...
output:
160 1 4 3 8 11 12 14 16 12 15 7 14 17 18 22 23 18 22 27 28 26 27 29 30 30 31 27 30 20 28 13 23 33 35...
result:
ok ok,using 585 times
Test #2:
score: 0
Accepted
time: 0ms
memory: 1248kb
input:
25 21264 13876 11861 12802 18452 3136 17660 21163 14140 20632 25998 22051 10612 12680 7873 23249 274...
output:
49 1 2 2 4 5 6 4 5 8 9 11 13 9 11 5 9 20 22 24 25 21 24 16 22 7 18 1 4 7 8 8 9 9 10 2 9 3 4 2 3 1 2 ...
result:
ok ok,using 145 times
Test #3:
score: 0
Accepted
time: 0ms
memory: 1256kb
input:
95 26373 31391 7777 12225 25301 24166 2461 4926 15751 18727 29175 18511 17455 16025 16845 6723 3477 ...
output:
278 1 3 2 4 3 9 13 14 14 17 22 23 23 24 20 23 16 21 6 18 25 26 32 33 26 32 44 45 46 47 47 48 45 47 3...
result:
ok ok,using 1063 times
Test #4:
score: 0
Accepted
time: 0ms
memory: 1256kb
input:
100 15104 1621 22502 12704 13109 9592 1390 22280 23468 26863 23084 10981 20492 7842 12883 16636 2565...
output:
278 3 4 4 7 11 12 8 11 7 8 17 18 16 17 21 22 23 24 24 25 22 24 17 23 8 20 26 28 27 31 33 34 34 35 36...
result:
ok ok,using 1105 times
Test #5:
score: 0
Accepted
time: 0ms
memory: 1256kb
input:
100 13822 19801 16537 25492 24250 30303 18588 13044 8538 23642 864 10878 16671 5509 13062 15457 2577...
output:
276 10 12 2 11 17 18 18 19 20 25 19 22 6 21 28 31 33 34 34 37 30 35 39 40 43 44 40 43 45 50 42 47 33...
result:
ok ok,using 1100 times
Subtask #2:
score: 40
Accepted
Test #6:
score: 40
Accepted
time: 0ms
memory: 1268kb
input:
197 10471 12679 10817 27406 21095 21068 9625 5396 14548 20977 29338 17674 30961 25672 4782 22715 301...
output:
613 5 7 4 5 5 9 14 15 20 21 21 22 15 21 7 16 26 27 27 29 30 32 29 30 34 35 37 38 35 37 30 36 39 41 4...
result:
ok ok,using 2733 times
Test #7:
score: 0
Accepted
time: 1ms
memory: 1276kb
input:
354 28133 31628 5619 8961 1003 9779 27591 14336 31618 17755 6349 17570 25604 24107 23136 21537 16494...
output:
1312 1 3 2 6 7 8 10 11 8 10 5 8 22 23 13 22 7 16 25 26 26 29 30 34 29 31 36 37 38 39 39 40 37 39 41 ...
result:
ok ok,using 6184 times
Test #8:
score: 0
Accepted
time: 0ms
memory: 1288kb
input:
512 14563 17808 18597 4341 12143 30490 13558 4331 30512 15302 14593 3642 21783 21775 23315 5766 1661...
output:
2039 3 4 2 3 6 8 3 7 9 10 10 12 15 16 13 15 12 13 6 12 17 18 19 20 18 19 19 22 29 31 28 29 21 28 10 ...
result:
ok ok,using 10122 times
Test #9:
score: 0
Accepted
time: 0ms
memory: 1356kb
input:
1000 1502 12015 26522 985 16804 3210 22284 28860 17265 9237 23503 15006 9625 30582 12808 25544 5298 ...
output:
4427 3 4 5 6 4 5 9 10 11 12 10 11 14 15 11 14 5 12 18 22 25 28 31 32 29 31 27 29 20 27 9 22 39 40 38...
result:
ok ok,using 24525 times
Test #10:
score: 0
Accepted
time: 1ms
memory: 1360kb
input:
1000 220 30195 7500 27597 28712 10097 25659 20392 16159 6016 31747 14902 5036 29017 31162 24365 2359...
output:
4481 2 3 5 6 3 5 11 12 12 13 4 12 17 18 19 20 18 19 21 24 19 22 25 26 26 29 21 26 8 22 43 44 41 43 4...
result:
ok ok,using 24499 times
Subtask #3:
score: 30
Accepted
Test #11:
score: 30
Accepted
time: 13ms
memory: 1932kb
input:
29160 3 3 5 5 4 4 5 1 3 2 5 1 4 3 2 3 1 2 1 5 4 4 4 0 2 3 4 2 1 4 4 5 3 3 5 4 2 4 4 1 3 5 1 1 2 2 2 ...
output:
38188 7 8 5 7 3 5 11 12 13 14 14 15 12 14 4 13 23 24 24 26 27 28 28 29 26 28 20 27 9 24 32 33 30 32 ...
result:
ok ok,using 514564 times
Test #12:
score: 0
Accepted
time: 9ms
memory: 1936kb
input:
29654 4 0 1 1 0 2 2 3 2 4 2 3 0 1 2 1 1 0 2 2 5 2 5 4 4 5 0 2 3 4 2 5 1 1 0 2 2 2 2 5 3 5 2 1 0 1 5 ...
output:
38628 1 2 2 4 4 8 10 12 12 15 8 14 21 22 23 29 22 25 14 24 30 31 32 33 31 32 32 37 40 41 42 43 43 44...
result:
ok ok,using 522943 times
Test #13:
score: 0
Accepted
time: 11ms
memory: 1632kb
input:
23759 0 4 4 5 0 0 4 2 0 2 5 4 0 1 0 1 2 3 4 1 5 1 1 2 4 2 4 3 4 3 0 3 3 3 2 2 4 1 4 3 1 4 5 1 3 2 1 ...
output:
30993 4 5 5 6 2 5 7 8 8 9 9 10 4 9 19 20 20 24 7 22 25 26 29 30 26 29 28 36 37 38 38 41 43 44 44 45 ...
result:
ok ok,using 408575 times
Test #14:
score: 0
Accepted
time: 11ms
memory: 1956kb
input:
32000 1 5 4 5 2 4 0 4 5 3 2 2 4 0 3 2 4 3 0 5 1 1 1 5 4 3 0 4 3 1 2 0 0 0 4 4 5 5 4 2 4 2 0 1 3 2 4 ...
output:
41179 6 7 2 6 9 10 10 12 13 14 14 16 12 15 4 14 17 18 18 19 19 23 25 26 26 27 27 32 22 30 10 27 39 4...
result:
ok ok,using 567288 times
Test #15:
score: 0
Accepted
time: 5ms
memory: 1952kb
input:
32000 2 5 2 0 0 2 5 2 0 0 1 2 0 5 3 4 0 1 5 2 3 4 5 3 1 5 1 4 5 2 5 0 1 4 0 1 3 0 5 2 2 2 2 5 0 1 1 ...
output:
41237 2 4 7 8 4 7 14 15 7 14 19 20 23 24 22 23 20 22 26 27 29 30 31 32 30 31 27 30 22 28 13 25 34 36...
result:
ok ok,using 567668 times
Subtask #4:
score: 10
Accepted
Test #16:
score: 10
Accepted
time: 40ms
memory: 3344kb
input:
25162 6548 134 11176 15393 24121 2053 29582 27616 22505 27930 3608 3082 22087 20841 5912 29959 21750...
output:
165559 5 6 8 12 6 9 14 15 17 18 15 17 20 22 23 25 21 23 16 21 8 17 26 27 27 30 36 38 35 36 28 35 39 ...
result:
ok ok,using 1307092 times
Test #17:
score: 0
Accepted
time: 20ms
memory: 2200kb
input:
13372 26001 8161 11243 31249 17641 3471 20342 11205 10364 6910 16562 14549 14518 1517 14171 739 2413...
output:
82532 1 2 2 3 5 6 3 5 11 14 4 13 17 18 18 20 22 24 23 27 20 25 10 23 28 29 30 31 29 30 32 33 30 32 3...
result:
ok ok,using 610381 times
Test #18:
score: 0
Accepted
time: 49ms
memory: 2252kb
input:
19761 26255 27109 5277 12037 28781 24950 6309 20913 27434 4457 25574 14446 10697 31185 14349 17737 2...
output:
127349 1 3 2 4 6 7 9 10 7 9 3 7 11 12 12 13 14 15 13 14 19 20 16 19 14 16 5 14 23 24 26 27 29 30 27 ...
result:
ok ok,using 979941 times
Test #19:
score: 0
Accepted
time: 50ms
memory: 3392kb
input:
32000 30347 31469 13058 20205 19829 2372 10241 20616 25222 30014 29774 414 1519 26519 882 14611 2885...
output:
214347 1 3 5 6 6 7 2 6 11 12 9 11 14 16 10 15 4 12 17 19 18 23 26 28 29 30 30 32 28 31 21 30 8 26 33...
result:
ok ok,using 1737836 times
Test #20:
score: 0
Accepted
time: 51ms
memory: 3392kb
input:
32000 29833 18417 7092 14816 30969 23083 28208 11380 24884 26793 6017 311 28930 24186 1060 13432 297...
output:
214149 1 4 7 8 5 7 3 5 9 12 13 16 11 14 4 12 17 18 18 19 21 22 23 24 22 23 19 22 28 31 21 30 8 26 34...
result:
ok ok,using 1736941 times