QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#307627 | #962. Thanks to MikeMirzayanov | yllcm | AC ✓ | 21ms | 4956kb | C++14 | 2.8kb | 2024-01-18 21:55:15 | 2024-01-18 21:55:16 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define db double
#define ull unsigned long long
#define pb push_back
#define pii pair<int, int>
#define FR first
#define SE second
using namespace std;
inline int read() {
int x = 0; bool op = false;
char c = getchar();
while(!isdigit(c))op |= (c == '-'), c = getchar();
while(isdigit(c))x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
return op ? -x : x;
}
const int N = 2e4 + 10;
int n, type;
int a[N];
vector<vector<int>> ans;
void doit(vector<int> d) {
// if(type)reverse(d.begin(), d.end());
int sum = 0;
for(int u : d)reverse(a + 1 + sum, a + 1 + sum + u), sum += u;
if(type)reverse(d.begin(), d.end());
if(d.size() > 1)ans.pb(d); type ^= 1;
return ;
}
int main() {
n = read();
for(int i = 1; i <= n; i++)a[i] = read();
vector<int> rg = {n};
for(int w = 15; ~w; w--) {
vector<int> d;
auto work = [&](int l, int r) {
// cerr << "work:" << l << ' ' << r << endl;
vector<int> seq;
for(int i = l; i <= r; i++) {
int k = i;
while(k < r && (a[k + 1] >> w & 1) == (a[k] >> w & 1))k++;
seq.pb(k - i + 1); i = k;
}
// cerr << seq.size() << endl;
if(seq.size() == 1)return d.pb(seq[0]), seq[0];
if(seq.size() == 2) {
if(a[l] >> w & 1)return d.pb(seq[0] + seq[1]), -1;
else return d.pb(seq[0]), d.pb(seq[1]), seq[0];
}
if(seq.size() == 3) {
if(a[l] >> w & 1)d.pb(seq[0] + seq[1]), d.pb(seq[2]);
else d.pb(seq[0]), d.pb(seq[1] + seq[2]);
}
else {
int o = 0;
for(int i = 0; i < seq.size(); i += 2, o ^= 1) {
if(i + 1 < seq.size() && o)d.pb(seq[i] + seq[i + 1]);
else {
d.pb(seq[i]);
if(i + 1 < seq.size())d.pb(seq[i + 1]);
}
}
}
return -1;
};
int o = 0;
while(true) {
int flg = 1, sum = 0;
vector<pii> nr;
vector<int>().swap(d);
for(auto u : rg) {
int res = work(sum + 1, sum + u);
flg &= (res != -1);
nr.pb({res, u - res});
sum += u;
}
if(flg) {
vector<int>().swap(rg);
for(auto t : nr) {if(t.FR)rg.pb(t.FR); if(t.SE)rg.pb(t.SE);}
break;
}
// for(int i = 1; i <= n; i++)cerr << a[i] << ' '; cerr << endl;
doit(d);
}
// cerr << w << ' ' << type << endl;
// for(int i = 1; i <= n; i++)cerr << a[i] << ' '; cerr << endl;
// for(int u : rg)cerr << u << ' '; cerr << endl;
}
if(type)doit(vector<int>(n, 1));
for(int i = 1; i <= n; i++)assert(a[i] == i);
printf("%lu\n", ans.size());
for(auto t : ans) {
printf("%lu ", t.size());
for(int u : t)printf("%d ", u); putchar('\n');
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3676kb
input:
4 3 1 2 4
output:
2 3 2 1 1 3 1 2 1
result:
ok OK
Test #2:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
6 6 5 4 3 2 1
output:
1 6 1 1 1 1 1 1
result:
ok OK
Test #3:
score: 0
Accepted
time: 1ms
memory: 3668kb
input:
1 1
output:
0
result:
ok OK
Test #4:
score: 0
Accepted
time: 0ms
memory: 3732kb
input:
10 3 8 7 4 6 2 9 10 1 5
output:
6 4 1 1 6 2 2 9 1 3 2 5 3 7 2 1 2 1 1 2 1 6 1 2 3 1 2 1 7 1 2 1 1 2 2 1
result:
ok OK
Test #5:
score: 0
Accepted
time: 1ms
memory: 3972kb
input:
20 2 13 11 1 19 12 15 3 9 4 14 18 17 7 16 8 6 10 5 20
output:
14 6 4 1 8 1 1 5 4 4 9 3 4 2 4 16 10 5 1 2 1 2 2 1 3 2 1 7 1 3 6 2 2 1 5 5 5 1 7 6 1 3 1 14 5 11 4 1 1 3 2 2 1 1 2 2 1 7 1 3 3 6 2 4 1 6 1 4 4 4 6 1 12 1 2 1 3 4 1 1 2 1 1 2 1 11 1 3 1 3 1 2 2 2 2 2 1 15 1 1 1 2 1 1 1 1 2 2 2 1 1 2 1 20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
result:
ok OK
Test #6:
score: 0
Accepted
time: 1ms
memory: 3720kb
input:
50 42 29 21 50 27 23 7 43 46 13 37 1 35 31 30 32 44 19 11 38 10 20 33 15 25 40 48 12 34 28 36 14 8 2 9 24 16 39 17 49 26 41 18 3 4 45 47 6 22 5
output:
20 23 1 2 4 2 1 2 1 2 4 1 2 3 2 1 2 1 6 2 1 1 4 2 3 12 6 4 2 9 2 3 7 4 2 5 5 1 7 1 7 13 6 9 11 3 4 7 27 15 1 2 32 18 22 4 1 3 8 1 2 1 3 1 1 4 1 2 3 2 1 2 1 1 2 4 2 13 2 5 4 2 4 5 4 2 3 2 2 11 4 8 17 2 3 2 7 10 7 2 6 2 13 13 3 16 3 4 3 16 14 17 25 2 2 3 2 1 4 1 1 1 4 1 1 2 1 1 2 1 1 1 1 4 2...
result:
ok OK
Test #7:
score: 0
Accepted
time: 1ms
memory: 3724kb
input:
100 21 42 70 62 37 99 52 55 38 12 95 23 48 18 9 88 30 49 40 60 47 67 27 63 79 75 16 81 22 58 20 2 56 89 76 98 26 14 72 51 7 39 45 54 50 3 13 90 24 33 91 93 15 87 73 25 41 64 29 100 10 28 36 94 46 32 82 61 6 59 69 35 57 80 74 77 17 86 71 66 84 11 96 85 43 65 68 31 44 34 92 1 53 4 97 19 8 78 5 83
output:
26 38 2 1 3 4 1 5 5 1 4 1 1 8 2 1 9 2 2 3 2 1 2 3 1 3 3 1 5 1 4 3 1 2 4 3 1 3 1 1 20 1 3 8 3 2 9 4 5 6 2 3 14 2 7 7 3 9 8 2 2 11 2 4 22 10 6 17 9 10 10 9 1 6 15 15 22 35 11 2 4 2 21 63 14 2 98 2 34 1 1 2 2 2 7 3 1 4 2 4 3 1 4 2 4 1 2 1 3 3 1 4 4 1 4 1 5 11 1 2 3 1 9 19 9 1 4 17 2 4 4 7 5 2 7 ...
result:
ok OK
Test #8:
score: 0
Accepted
time: 1ms
memory: 3776kb
input:
120 120 72 23 35 8 87 24 94 101 61 21 18 112 111 73 36 7 105 118 64 40 56 108 1 66 76 77 33 119 53 31 9 89 86 50 96 85 70 30 102 81 13 10 49 78 114 117 57 20 2 98 115 59 43 16 45 63 44 116 54 58 32 68 26 97 5 27 46 4 107 22 95 47 62 17 51 84 74 25 34 104 91 39 106 12 103 79 11 90 109 3 15 88 38 71 4...
output:
26 49 2 3 2 2 3 5 3 2 2 3 1 4 2 1 4 2 3 6 2 6 4 1 1 5 1 1 5 2 2 3 1 1 3 2 2 2 1 1 2 1 1 4 3 2 5 1 1 3 1 25 2 6 5 6 4 2 2 7 2 3 6 5 2 7 9 5 11 2 3 8 3 6 8 4 2 13 2 9 16 7 8 24 4 8 11 6 4 16 5 7 13 24 13 14 38 16 2 4 2 38 55 25 2 55 65 48 2 1 4 1 1 2 1 5 7 2 3 3 2 1 2 1 1 7 1 3 3 3 2 5 1 2 8 2 2...
result:
ok OK
Test #9:
score: 0
Accepted
time: 1ms
memory: 4068kb
input:
130 64 8 50 36 32 109 91 53 113 19 86 63 4 15 117 46 130 61 72 107 126 31 9 120 87 111 128 94 82 33 45 89 103 29 85 62 98 18 101 73 38 67 77 119 44 105 92 100 40 121 20 57 84 123 114 25 55 95 43 78 11 1 115 90 83 129 52 116 10 65 17 59 7 22 5 122 80 124 118 41 127 58 16 69 88 35 66 106 51 47 3 96 48...
output:
32 6 16 1 10 38 1 64 4 64 48 2 16 2 16 114 57 3 2 2 3 1 1 2 2 1 4 3 1 3 3 2 2 1 2 4 3 2 4 1 1 6 4 1 3 2 1 5 1 7 2 1 1 4 1 1 2 1 1 4 1 2 3 1 2 4 1 4 3 1 1 4 1 1 30 1 2 7 5 4 5 4 4 4 2 4 4 8 3 7 3 5 10 3 6 5 3 4 9 2 3 5 3 2 3 16 3 7 6 5 16 8 9 16 6 10 10 6 7 15 5 1 10 1 11 28 14 15 34 11 8 5 3 ...
result:
ok OK
Test #10:
score: 0
Accepted
time: 1ms
memory: 3988kb
input:
200 104 2 22 101 71 156 31 51 154 27 105 102 162 21 113 192 114 64 176 174 198 76 53 6 14 79 130 72 99 38 25 95 175 112 43 39 63 88 187 47 137 77 26 80 56 11 186 151 172 91 144 116 152 55 52 48 199 7 189 98 128 40 178 121 45 32 194 191 134 103 197 82 181 37 59 42 168 61 12 136 115 97 20 180 145 46 1...
output:
34 78 5 1 3 3 1 3 2 3 6 5 1 6 1 1 8 1 1 2 3 1 2 1 1 2 3 3 2 1 1 4 2 1 5 2 1 3 1 1 3 3 1 5 1 1 2 4 1 5 1 1 6 4 2 4 2 1 3 3 2 3 2 1 2 5 4 4 4 2 4 4 1 4 2 1 3 1 1 4 40 4 4 2 5 8 4 6 12 2 4 7 3 3 14 2 5 7 2 2 10 2 2 8 3 5 4 4 4 4 2 4 8 4 6 12 4 4 7 2 5 21 5 4 15 16 6 14 6 6 13 7 7 11 10 7 18 8 8 18 11...
result:
ok OK
Test #11:
score: 0
Accepted
time: 1ms
memory: 3840kb
input:
1000 266 497 345 212 566 310 166 640 865 595 225 315 837 619 999 638 652 599 772 515 815 32 416 591 649 476 364 363 915 75 293 569 960 320 545 824 422 433 970 52 894 148 585 713 429 872 330 838 708 257 122 925 100 178 530 17 132 740 40 760 856 712 414 300 296 962 902 424 65 922 733 820 623 295 776 3...
output:
54 384 4 1 5 2 9 4 3 1 4 1 2 3 1 1 3 1 1 3 2 1 3 2 1 4 3 2 6 1 1 2 1 2 6 4 5 3 4 2 2 4 3 3 2 1 2 1 3 6 2 4 4 2 1 8 3 1 4 1 1 2 3 1 7 1 1 2 2 4 4 5 2 2 1 1 6 3 2 4 1 1 2 1 1 3 3 2 2 1 2 3 3 1 4 2 1 4 1 1 2 1 1 4 1 1 3 1 2 7 1 1 4 9 2 5 1 1 4 1 1 3 1 1 2 3 3 4 2 2 2 2 3 5 2 1 5 1 1 3 3 3 2 3 1 3 3 1 3...
result:
ok OK
Test #12:
score: 0
Accepted
time: 4ms
memory: 3976kb
input:
3535 3521 780 1120 790 540 803 1342 3087 280 382 938 2398 1467 1959 645 1259 371 830 3399 1237 3356 3533 903 1721 2564 1545 3222 1184 1473 1970 1483 609 3349 571 536 591 1598 2380 1993 2527 71 1303 2278 1233 264 1262 3428 2133 307 1793 2678 2857 3029 3149 2197 876 1621 1418 1802 111 1394 406 3422 27...
output:
76 1282 1 6 4 1 6 2 2 2 2 1 5 5 1 1 3 1 3 4 5 7 4 2 1 6 1 3 3 4 2 3 1 2 4 1 1 6 1 1 4 1 1 5 1 1 6 2 1 2 1 1 4 3 3 5 1 2 3 1 1 2 1 1 2 2 1 4 2 2 2 1 3 3 3 3 8 5 1 2 1 2 2 3 2 4 1 6 7 1 1 3 1 1 3 5 2 2 1 4 3 1 1 5 1 3 4 2 4 4 6 1 4 2 5 3 1 3 2 1 3 5 3 3 2 1 5 7 1 5 6 1 1 3 1 2 3 1 1 2 1 1 4 1 2 3 1 3 ...
result:
ok OK
Test #13:
score: 0
Accepted
time: 10ms
memory: 4180kb
input:
9876 8940 3942 9482 6904 9011 3552 9362 3393 930 6486 6386 4279 8280 2433 550 4981 4612 6715 8963 9634 2788 3423 1318 8155 3248 4424 9048 5812 4975 4036 8318 8334 4224 2762 2535 8447 6668 3900 146 1979 2676 7813 5713 8529 1327 2747 906 6213 3706 5326 222 4290 1731 8908 6883 7754 8160 9383 7450 1760 ...
output:
102 2087 1 1 2 1 1 6 1 5 8 1 3 5 1 7 10 1 3 4 1 10 2 2 1 4 1 1 14 1 3 8 2 1 4 1 2 9 1 6 3 1 2 5 1 4 15 1 4 11 3 12 4 1 4 8 1 6 3 1 1 5 2 20 10 2 2 6 1 5 15 2 5 7 1 4 5 2 3 3 1 2 5 1 9 5 1 1 2 1 1 8 1 1 7 2 1 7 2 10 2 2 2 23 1 3 7 1 1 10 2 7 5 1 3 10 1 3 3 1 13 3 2 3 10 1 3 4 1 26 4 1 6 5 1 3 5 3 3 9...
result:
ok OK
Test #14:
score: 0
Accepted
time: 9ms
memory: 4576kb
input:
12999 9367 6922 2753 1285 354 11783 941 4220 2425 12409 4623 5616 8731 5155 7125 6530 6031 2039 1558 162 1656 9857 5346 12638 4184 8088 386 3880 2146 8445 12235 9436 7606 11663 10496 4755 333 3515 3845 8908 3514 7121 3886 10240 10569 10738 9244 9118 12185 6188 9822 2208 1814 10513 10381 2807 5889 17...
output:
104 4556 1 4 4 1 2 9 1 1 6 3 1 6 1 3 7 1 2 8 1 2 6 2 1 2 1 7 7 1 1 3 1 3 3 1 1 2 1 4 2 1 7 3 1 5 2 1 8 4 1 1 3 4 4 2 2 4 4 1 2 3 1 12 2 4 3 2 1 1 4 2 1 4 1 7 2 1 1 3 2 1 10 1 1 2 1 5 2 1 10 3 1 1 3 3 4 3 1 3 2 1 3 5 1 1 4 2 1 8 3 2 3 2 1 5 1 7 4 2 8 3 2 2 4 2 1 2 1 1 4 2 2 2 1 5 7 1 3 5 4 1 3 1 4 3 ...
result:
ok OK
Test #15:
score: 0
Accepted
time: 20ms
memory: 4956kb
input:
19875 1909 9118 6273 13408 8288 2787 3440 12186 3615 2075 14373 2287 7102 13197 9163 11896 1042 11024 14067 14824 1750 9712 152 7448 4766 3784 8935 2866 10542 12696 19254 10844 14519 13229 14677 6007 5599 3398 19092 10298 17650 16560 1877 7298 3206 18047 19498 5654 13110 16391 4555 15442 19393 9280 ...
output:
118 4365 30 1 8 1 2 5 2 1 3 4 1 2 6 1 9 2 1 3 4 1 3 4 1 4 4 1 3 13 1 25 1 1 4 7 1 2 13 2 3 2 1 6 6 2 3 6 1 3 7 1 14 3 1 2 2 1 6 11 1 7 6 1 7 9 2 2 2 1 5 3 1 23 3 1 4 12 2 4 3 1 2 7 1 3 5 1 17 1 2 4 3 1 4 2 1 2 2 1 14 3 1 4 1 1 2 4 1 4 4 1 8 2 1 9 13 1 4 1 1 9 7 2 6 1 1 9 9 2 5 2 1 2 1 1 29 7 4 3 1 1...
result:
ok OK
Test #16:
score: 0
Accepted
time: 21ms
memory: 4768kb
input:
20000 15515 4495 17804 9254 14476 11181 8570 17799 15408 18550 2853 19132 12707 12414 8288 5175 6837 11709 8577 13179 5171 3509 419 15496 10365 6791 11342 14312 2498 7334 5601 10178 3714 976 10077 8368 3916 541 7960 4202 9960 19251 4868 12089 12892 12474 9529 14071 15392 13185 9462 1300 12436 10390 ...
output:
118 4402 2 1 5 1 1 2 29 1 24 9 1 4 3 1 2 5 1 5 15 1 6 5 1 2 2 1 12 1 1 5 1 1 5 4 1 22 8 1 6 2 1 3 6 1 10 9 1 4 1 1 13 12 3 13 3 1 7 1 1 5 8 1 8 5 1 6 3 1 5 8 1 15 23 1 2 3 1 3 1 1 10 2 1 2 4 1 5 4 2 10 2 1 28 1 1 10 11 1 9 3 1 3 8 2 10 2 1 20 7 1 20 5 2 13 12 1 7 4 1 4 7 1 9 6 1 9 1 1 4 2 1 5 9 2 3 ...
result:
ok OK