QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#223602 | #1968. Science Fiction | BUET_Twilight# | AC ✓ | 7ms | 3780kb | C++23 | 3.1kb | 2023-10-22 13:55:46 | 2023-10-22 13:55:46 |
Judging History
answer
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace __gnu_pbds;
using namespace std;
#define getbit(n, i) (((n) & (1LL << (i))) != 0)
#define setbit0(n, i) ((n) & (~(1LL << (i))))
#define setbit1(n, i) ((n) | (1LL << (i)))
#define togglebit(n, i) ((n) ^ (1LL << (i)))
#define lastone(n) ((n) & (-(n)))
char gap = 32;
#define int long long
#define ll long long
#define lll __int128_t
#define pb push_back
#define pii pair<int,int>
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll hashPrime = 1610612741;
const int N = 1120;
int ara[N];
int sorted[N];
pii target[N];
vector<pii> res;
void solve(int n) {
if (n == 1) return;
for (int i=0; i<n; i++) if (ara[i] == sorted[n-1]) {
if (i != n-1) {
int cur = i;
// take i to zero
for (int pos = 0; pos <= 12; pos++) {
if ((cur >> pos) & 1) {
res.pb({cur, cur ^ (1 << pos)});
swap(ara[cur], ara[cur ^ (1 << pos)]);
cur ^= (1 << pos);
}
}
cur = 0;
// take 0 to n-1
for (int pos = 0; pos <= 12; pos++) {
if (((n-1) >> pos) & 1) {
res.pb({cur, cur ^ (1 << pos)});
swap(ara[cur], ara[cur ^ (1 << pos)]);
cur ^= (1 << pos);
}
}
}
solve(n-1);
return;
}
}
void solve(){
int n;
cin >> n;
n = 1<<n;
for (int i=0; i<n; i++) cin >> ara[i];
for (int i=0; i<n; i++) sorted[i] = ara[i];
sort(sorted, sorted + n);
solve(n);
// for(int i=0;i<n;i++) target[i] = {ara[i], i};
// sort(target, target+n);
// for(int i=0;i<n;i++) cur[i] = target[i].second;
// for (int i=n-1; i>=0; i--) {
// //if (ara[i] == target[i].first) continue;
// int pos = cur[i];
// int mul = 1;
// for(int b=0;b<=12;b++){
// if( mul & pos ){
// res.pb({pos, pos^mul});
// //cout<<pos<<" "<<(pos^mul)<<endl;
// swap(cur[pos], cur[pos^mul]);
// pos ^= mul;
// }
// mul = mul<<1;
// }
// pos = 0;
// mul = 1;
// for(int b=0;b<=12;b++){
// if( mul & i ){
// res.pb({pos, pos^mul});
// // cout<<pos<<" "<<(pos^mul)<<endl;
// swap(cur[pos], cur[pos^mul]);
// pos ^= mul;
// }
// mul <<= 1;
// }
// }
cout<<res.size()<<endl;
for(auto p: res) cout << p.first << " " << p.second << endl;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3584kb
input:
2 3 2 10 4
output:
6 2 0 0 1 1 3 1 0 0 2 0 1
result:
ok nice! 6 moves
Test #2:
score: 0
Accepted
time: 1ms
memory: 3456kb
input:
1 10 100
output:
0
result:
ok nice! 0 moves
Test #3:
score: 0
Accepted
time: 0ms
memory: 3428kb
input:
1 824838 992401
output:
0
result:
ok nice! 0 moves
Test #4:
score: 0
Accepted
time: 0ms
memory: 3400kb
input:
2 208395 17211 250690 874014
output:
1 0 1
result:
ok nice! 1 moves
Test #5:
score: 0
Accepted
time: 0ms
memory: 3536kb
input:
8 991318 655714 983340 496226 752852 888298 572661 729100 426124 437775 8096 28612 303846 295897 970760 179029 702449 407420 945406 352294 960516 484993 724888 495235 156841 451864 95506 869159 61631 296168 279240 260130 901551 726353 298872 221580 982372 394731 720187 656498 595457 381795 759187 36...
output:
1814 0 1 1 3 3 7 7 15 15 31 31 63 63 127 127 255 164 160 160 128 128 0 0 2 2 6 6 14 14 30 30 62 62 126 126 254 224 192 192 128 128 0 0 1 1 5 5 13 13 29 29 61 61 125 125 253 128 0 0 4 4 12 12 28 28 60 60 124 124 252 36 32 32 0 0 1 1 3 3 11 11 27 27 59 59 123 123 251 169 168 168 160 160 128 128 0 0 2 ...
result:
ok nice! 1814 moves
Test #6:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
9 888559 111203 65032 290846 22133 226267 707470 14065 736516 622251 346047 555707 482074 680230 613967 497441 449554 967825 651070 678493 472313 583791 720445 224302 300743 198731 973353 657745 445065 428890 915188 532221 601100 975552 252972 265343 797188 997748 751515 244459 880581 499279 192690 ...
output:
4100 37 36 36 32 32 0 0 1 1 3 3 7 7 15 15 31 31 63 63 127 127 255 255 511 381 380 380 376 376 368 368 352 352 320 320 256 256 0 0 2 2 6 6 14 14 30 30 62 62 126 126 254 254 510 73 72 72 64 64 0 0 1 1 5 5 13 13 29 29 61 61 125 125 253 253 509 504 496 496 480 480 448 448 384 384 256 256 0 0 4 4 12 12 2...
result:
ok nice! 4100 moves
Test #7:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
10 46982 476817 496931 560433 461240 750978 947847 814814 659646 506842 759616 931346 752705 449448 557667 164565 805585 139966 935551 743130 400827 826593 316939 597171 566302 42318 283510 548860 557699 464391 241748 310653 488228 677001 434005 590123 338841 574036 303991 216552 454974 914883 31282...
output:
9322 549 548 548 544 544 512 512 0 0 1 1 3 3 7 7 15 15 31 31 63 63 127 127 255 255 511 511 1023 671 670 670 668 668 664 664 656 656 640 640 512 512 0 0 2 2 6 6 14 14 30 30 62 62 126 126 254 254 510 510 1022 631 630 630 628 628 624 624 608 608 576 576 512 512 0 0 1 1 5 5 13 13 29 29 61 61 125 125 253...
result:
ok nice! 9322 moves
Test #8:
score: 0
Accepted
time: 0ms
memory: 3676kb
input:
10 949240 35612 460205 974087 338042 271803 334025 63491 750807 279433 899420 120333 875712 396956 17331 903377 75543 841309 975578 209064 858085 265088 990752 382189 453875 707785 91883 487626 999153 989617 672899 730478 89929 619621 96174 915274 438090 705909 682206 236298 574666 885407 168720 540...
output:
9330 951 950 950 948 948 944 944 928 928 896 896 768 768 512 512 0 0 1 1 3 3 7 7 15 15 31 31 63 63 127 127 255 255 511 511 1023 28 24 24 16 16 0 0 2 2 6 6 14 14 30 30 62 62 126 126 254 254 510 510 1022 188 184 184 176 176 160 160 128 128 0 0 1 1 5 5 13 13 29 29 61 61 125 125 253 253 509 509 1021 964...
result:
ok nice! 9330 moves
Test #9:
score: 0
Accepted
time: 4ms
memory: 3740kb
input:
10 746874 671481 787373 91722 286998 843370 287027 699571 566633 92904 121270 84581 172807 118213 566935 494171 96174 128894 912103 167003 563084 240573 445148 595153 430540 871105 407520 875615 374793 147544 58778 979552 146961 97898 511796 530999 496562 478923 730985 885285 94569 490511 331797 927...
output:
9351 138 136 136 128 128 0 0 1 1 3 3 7 7 15 15 31 31 63 63 127 127 255 255 511 511 1023 669 668 668 664 664 656 656 640 640 512 512 0 0 2 2 6 6 14 14 30 30 62 62 126 126 254 254 510 510 1022 1017 1016 1016 1008 1008 992 992 960 960 896 896 768 768 512 512 0 0 1 1 5 5 13 13 29 29 61 61 125 125 253 25...
result:
ok nice! 9351 moves
Test #10:
score: 0
Accepted
time: 0ms
memory: 3724kb
input:
10 546693 308346 853356 12952 842161 797467 832954 207696 730371 27541 94381 419145 35259 663666 987797 42166 362364 136282 161216 934180 391497 780167 195044 636218 940656 362727 31072 839926 412136 570431 834451 594285 517357 298316 891244 707769 86006 662265 452173 697662 420751 904255 665271 730...
output:
9319 937 936 936 928 928 896 896 768 768 512 512 0 0 1 1 3 3 7 7 15 15 31 31 63 63 127 127 255 255 511 511 1023 677 676 676 672 672 640 640 512 512 0 0 2 2 6 6 14 14 30 30 62 62 126 126 254 254 510 510 1022 402 400 400 384 384 256 256 0 0 1 1 5 5 13 13 29 29 61 61 125 125 253 253 509 509 1021 467 46...
result:
ok nice! 9319 moves
Test #11:
score: 0
Accepted
time: 0ms
memory: 3536kb
input:
1 819419 113088
output:
1 0 1
result:
ok nice! 1 moves
Test #12:
score: 0
Accepted
time: 0ms
memory: 3484kb
input:
2 725964 552203 371378 344109
output:
4 0 1 1 3 0 2 0 1
result:
ok nice! 4 moves
Test #13:
score: 0
Accepted
time: 3ms
memory: 3680kb
input:
10 998030 997163 996957 993557 991195 989284 988223 985000 982700 982212 981058 981023 980199 979436 979287 977471 977098 977062 975229 974818 973741 973028 971101 970597 970328 969913 967931 967747 966649 966556 965497 963873 963808 962577 961661 960874 960527 958588 957708 956548 954238 954169 953...
output:
5120 0 1 1 3 3 7 7 15 15 31 31 63 63 127 127 255 255 511 511 1023 0 2 2 6 6 14 14 30 30 62 62 126 126 254 254 510 510 1022 0 1 1 5 5 13 13 29 29 61 61 125 125 253 253 509 509 1021 0 4 4 12 12 28 28 60 60 124 124 252 252 508 508 1020 0 1 1 3 3 11 11 27 27 59 59 123 123 251 251 507 507 1019 0 2 2 10 1...
result:
ok nice! 5120 moves
Test #14:
score: 0
Accepted
time: 4ms
memory: 3628kb
input:
10 998603 998169 997659 997290 997252 997151 996413 996391 996085 994969 990896 989802 987855 987448 986526 985933 984340 984041 983080 982762 982158 981412 980751 979775 979599 979224 976027 972756 972515 971272 971034 970460 969635 968618 968234 965740 964670 963272 958508 958370 956691 955586 955...
output:
5127 0 1 1 3 3 7 7 15 15 31 31 63 63 127 127 255 255 511 511 1023 0 2 2 6 6 14 14 30 30 62 62 126 126 254 254 510 510 1022 0 1 1 5 5 13 13 29 29 61 61 125 125 253 253 509 509 1021 0 4 4 12 12 28 28 60 60 124 124 252 252 508 508 1020 0 1 1 3 3 11 11 27 27 59 59 123 123 251 251 507 507 1019 0 2 2 10 1...
result:
ok nice! 5127 moves
Test #15:
score: 0
Accepted
time: 3ms
memory: 3604kb
input:
10 997893 997879 997251 996734 995681 995546 992657 991595 989691 989182 988758 988161 987328 985910 982385 982322 981361 980688 977437 977323 977313 977088 974645 973981 973504 972672 972559 969933 968924 968786 967992 967889 967840 966919 966755 966540 966241 965403 963714 962495 961713 960731 960...
output:
5140 0 1 1 3 3 7 7 15 15 31 31 63 63 127 127 255 255 511 511 1023 0 2 2 6 6 14 14 30 30 62 62 126 126 254 254 510 510 1022 0 1 1 5 5 13 13 29 29 61 61 125 125 253 253 509 509 1021 0 4 4 12 12 28 28 60 60 124 124 252 252 508 508 1020 0 1 1 3 3 11 11 27 27 59 59 123 123 251 251 507 507 1019 0 2 2 10 1...
result:
ok nice! 5140 moves
Test #16:
score: 0
Accepted
time: 6ms
memory: 3592kb
input:
10 999765 999540 999524 442723 783220 997869 997780 712090 996433 996257 996040 992566 991883 990874 990859 988633 582417 981709 937314 977988 84342 975260 591353 974330 974158 528281 973722 973625 973185 972643 971744 971507 969795 969647 969612 129152 966057 220244 964045 963969 963162 597812 4185...
output:
6437 0 1 1 3 3 7 7 15 15 31 31 63 63 127 127 255 255 511 511 1023 0 2 2 6 6 14 14 30 30 62 62 126 126 254 254 510 510 1022 0 1 1 5 5 13 13 29 29 61 61 125 125 253 253 509 509 1021 978 976 976 960 960 896 896 768 768 512 512 0 0 4 4 12 12 28 28 60 60 124 124 252 252 508 508 1020 219 218 218 216 216 2...
result:
ok nice! 6437 moves
Test #17:
score: 0
Accepted
time: 4ms
memory: 3728kb
input:
10 343821 998027 997026 996414 996404 773250 994500 859736 367107 993429 990586 714714 989540 989370 988330 987442 985869 478079 984828 984430 983909 424172 980184 438518 46043 797866 973296 972011 970740 969830 969509 968315 439027 967113 967029 966931 583530 47644 445131 961898 957808 957034 95661...
output:
6526 191 190 190 188 188 184 184 176 176 160 160 128 128 0 0 1 1 3 3 7 7 15 15 31 31 63 63 127 127 255 255 511 511 1023 0 2 2 6 6 14 14 30 30 62 62 126 126 254 254 510 510 1022 0 1 1 5 5 13 13 29 29 61 61 125 125 253 253 509 509 1021 0 4 4 12 12 28 28 60 60 124 124 252 252 508 508 1020 0 1 1 3 3 11 ...
result:
ok nice! 6526 moves
Test #18:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
10 999796 853861 338685 673431 997360 508676 986083 623206 985281 261993 455281 984165 806278 365801 983086 329846 836224 107339 978674 500414 976971 553047 53972 897597 287497 368894 966051 965944 25111 965071 162596 862808 962587 907148 336588 664453 959641 958947 958555 958124 954763 951778 95161...
output:
6909 0 1 1 3 3 7 7 15 15 31 31 63 63 127 127 255 255 511 511 1023 146 144 144 128 128 0 0 2 2 6 6 14 14 30 30 62 62 126 126 254 254 510 510 1022 676 672 672 640 640 512 512 0 0 1 1 5 5 13 13 29 29 61 61 125 125 253 253 509 509 1021 432 416 416 384 384 256 256 0 0 4 4 12 12 28 28 60 60 124 124 252 25...
result:
ok nice! 6909 moves
Test #19:
score: 0
Accepted
time: 7ms
memory: 3780kb
input:
10 695647 998457 256203 909670 982894 995992 995387 777482 994669 263854 989569 320493 252841 985455 530388 684573 983066 975593 891430 487880 349963 472375 372708 423420 974655 974388 974301 973152 950030 969447 679648 246707 966536 966376 965740 866666 30143 963819 961332 960251 209174 640492 2202...
output:
7366 855 854 854 852 852 848 848 832 832 768 768 512 512 0 0 1 1 3 3 7 7 15 15 31 31 63 63 127 127 255 255 511 511 1023 0 2 2 6 6 14 14 30 30 62 62 126 126 254 254 510 510 1022 758 756 756 752 752 736 736 704 704 640 640 512 512 0 0 1 1 5 5 13 13 29 29 61 61 125 125 253 253 509 509 1021 100 96 96 64...
result:
ok nice! 7366 moves
Test #20:
score: 0
Accepted
time: 0ms
memory: 3696kb
input:
10 258936 410937 283884 393387 982697 510737 680897 212979 153426 621625 795061 757773 244663 213121 74281 949123 983068 965482 433099 992440 514506 239699 440821 724409 311327 313198 852076 262928 788330 678441 506087 34286 809495 599525 970320 301833 969669 307223 871328 525355 797019 515257 10861...
output:
8767 765 764 764 760 760 752 752 736 736 704 704 640 640 512 512 0 0 1 1 3 3 7 7 15 15 31 31 63 63 127 127 255 255 511 511 1023 974 972 972 968 968 960 960 896 896 768 768 512 512 0 0 2 2 6 6 14 14 30 30 62 62 126 126 254 254 510 510 1022 727 726 726 724 724 720 720 704 704 640 640 512 512 0 0 1 1 5...
result:
ok nice! 8767 moves
Test #21:
score: 0
Accepted
time: 3ms
memory: 3724kb
input:
10 989539 264003 89801 336845 872805 363863 409608 722546 676281 871400 20414 972543 452474 858575 480750 639385 877845 432002 283043 932719 857101 146837 773058 438046 755472 383841 330153 180919 419122 281693 289297 988547 934831 667163 418404 844342 707371 773251 452058 951076 674998 598366 23071...
output:
9164 770 768 768 512 512 0 0 1 1 3 3 7 7 15 15 31 31 63 63 127 127 255 255 511 511 1023 237 236 236 232 232 224 224 192 192 128 128 0 0 2 2 6 6 14 14 30 30 62 62 126 126 254 254 510 510 1022 720 704 704 640 640 512 512 0 0 1 1 5 5 13 13 29 29 61 61 125 125 253 253 509 509 1021 385 384 384 256 256 0 ...
result:
ok nice! 9164 moves
Test #22:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
10 268981 729295 424417 366156 357055 175507 417152 240251 411056 912165 423865 278160 907860 413812 133438 626599 165355 660278 473775 6476 512331 250836 713169 750412 856144 665133 815985 636387 389359 22218 327844 551545 921825 35601 877698 671416 589514 192363 822860 403486 197385 617060 909896 ...
output:
9264 487 486 486 484 484 480 480 448 448 384 384 256 256 0 0 1 1 3 3 7 7 15 15 31 31 63 63 127 127 255 255 511 511 1023 979 978 978 976 976 960 960 896 896 768 768 512 512 0 0 2 2 6 6 14 14 30 30 62 62 126 126 254 254 510 510 1022 593 592 592 576 576 512 512 0 0 1 1 5 5 13 13 29 29 61 61 125 125 253...
result:
ok nice! 9264 moves