QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#212354#1968. Science Fictionvioalbert#AC ✓2ms3656kbC++172.0kb2023-10-13 15:11:112023-10-13 15:11:12

Judging History

你现在查看的是最新测评结果

  • [2023-10-13 15:11:12]
  • 评测
  • 测评结果:AC
  • 用时:2ms
  • 内存:3656kb
  • [2023-10-13 15:11:11]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()
#ifdef LOCAL
#define debug(...) __VA_ARGS__;
#else
#define debug(...) 24;
#endif

template<class A, class B>
ostream& operator<<(ostream &os, pair<A, B> &p);
template<class T>
ostream& operator<<(ostream &os, vector<T> &v);
template<class T, size_t sz>
ostream& operator<<(ostream &os, array<T, sz> &v);

template<class A, class B>
ostream& operator<<(ostream &os, pair<A, B> &p) {
  return os << '(' << p.first << ',' << p.second << ')';
}

template<class T>
ostream& operator<<(ostream &os, vector<T> &v) {
  os << '{';
  bool f = 0; for(auto &i : v) { if(f) os << ',';os << i; f = 1;}
  return os << '}';
}

template<class T, size_t sz>
ostream& operator<<(ostream &os, array<T, sz> &v) {
  os << '{';
  bool f = 0; for(auto &i : v) { if(f) os << ',';os << i; f = 1;}
  return os << '}';
}

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int n; cin >> n;
  int sz = 1<<n;
  vector<int> a(sz);
  for(int &i : a) cin >> i;
  vector<pair<int, int>> ans;
  for(int to = 0; to < sz; to++) {
    int mn = 1e9, from = sz;
    for(int i = to; i < sz; i++) {
      if(mn > a[i]) {
        mn = a[i];
        from = i;
      }
    }
    debug(cerr << "from = " << from << " to = " << to << '\n');
    for(int i = n-1; i >= 0; i--) {
      int bit = 1<<i;
      if((~from&bit) && (to&bit)) {
        debug(cerr << from << ' ' << (from | bit) << '\n');
        swap(a[from], a[from|bit]);
        ans.emplace_back(from, (from|bit));
        from |= bit;
      }
    }
    for(int i = n-1; i >= 0; i--) {
      int bit = 1<<i;
      if((from&bit) && (~to&bit)) {
        debug(cerr << from << ' ' << (from ^ bit) << '\n');
        swap(a[from], a[from^bit]);
        ans.emplace_back(from, (from^bit));
        from ^= bit;
      }
    }
    debug(cerr << a << '\n');
  }
  cout << ans.size() << '\n';
  for(auto [x, y] : ans)
    cout << x << ' ' << y << '\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3480kb

input:

2
3 2 10 4

output:

2
1 0
3 2

result:

ok nice! 2 moves

Test #2:

score: 0
Accepted
time: 0ms
memory: 3528kb

input:

1
10 100

output:

0

result:

ok nice! 0 moves

Test #3:

score: 0
Accepted
time: 0ms
memory: 3412kb

input:

1
824838 992401

output:

0

result:

ok nice! 0 moves

Test #4:

score: 0
Accepted
time: 0ms
memory: 3468kb

input:

2
208395 17211 250690 874014

output:

1
1 0

result:

ok nice! 1 moves

Test #5:

score: 0
Accepted
time: 1ms
memory: 3440kb

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:

914
62 30
30 14
14 6
6 2
2 0
10 11
11 3
3 1
77 79
79 15
15 7
7 3
3 2
44 46
46 47
47 15
15 7
7 3
69 5
5 4
10 14
14 15
15 7
7 5
210 214
214 86
86 22
22 6
54 55
55 23
23 7
137 9
9 8
138 139
139 11
11 9
171 43
43 11
11 10
195 203
203 75
75 11
194 202
202 206
206 78
78 14
14 12
117 125
125 61
61 29
29 13...

result:

ok nice! 914 moves

Test #6:

score: 0
Accepted
time: 1ms
memory: 3544kb

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:

2138
430 174
174 46
46 14
14 6
6 2
2 0
156 157
157 29
29 13
13 5
5 1
228 230
230 102
102 38
38 6
6 2
211 83
83 19
19 3
7 5
5 4
213 85
85 21
21 5
225 229
229 231
231 103
103 39
39 7
7 6
473 477
477 479
479 223
223 95
95 31
31 15
15 7
68 76
76 12
12 8
271 15
15 11
11 9
21 29
29 31
31 15
15 11
11 10
42...

result:

ok nice! 2138 moves

Test #7:

score: 0
Accepted
time: 1ms
memory: 3584kb

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:

4742
303 47
47 15
15 7
7 3
3 1
1 0
717 205
205 77
77 13
13 5
5 1
860 862
862 350
350 94
94 30
30 14
14 6
6 2
664 666
666 667
667 155
155 27
27 11
11 3
263 7
7 5
5 4
235 239
239 111
111 47
47 15
15 7
7 5
690 694
694 182
182 54
54 22
22 6
740 742
742 743
743 231
231 103
103 39
39 7
801 809
809 297
297...

result:

ok nice! 4742 moves

Test #8:

score: 0
Accepted
time: 1ms
memory: 3584kb

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:

4762
930 418
418 162
162 34
34 2
2 0
266 267
267 11
11 3
3 1
762 250
250 122
122 58
58 26
26 10
10 2
717 719
719 207
207 79
79 15
15 7
7 3
370 374
374 118
118 54
54 22
22 6
6 4
561 565
565 53
53 21
21 5
101 103
103 39
39 7
7 6
203 207
207 79
79 15
15 7
419 427
427 171
171 43
43 11
11 9
9 8
566 574
5...

result:

ok nice! 4762 moves

Test #9:

score: 0
Accepted
time: 0ms
memory: 3652kb

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:

4847
625 113
113 49
49 17
17 1
1 0
708 709
709 197
197 69
69 5
5 1
951 439
439 183
183 55
55 23
23 7
7 3
3 2
834 835
835 323
323 67
67 3
717 205
205 77
77 13
13 5
5 4
991 479
479 223
223 95
95 31
31 15
15 7
7 5
870 358
358 102
102 38
38 6
43 47
47 15
15 7
680 168
168 40
40 8
466 474
474 475
475 219
...

result:

ok nice! 4847 moves

Test #10:

score: 0
Accepted
time: 1ms
memory: 3528kb

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:

4775
503 247
247 119
119 55
55 23
23 7
7 3
3 1
1 0
774 775
775 263
263 7
7 3
3 1
793 795
795 283
283 27
27 11
11 3
3 2
332 334
334 335
335 79
79 15
15 7
7 3
77 13
13 5
5 4
923 927
927 415
415 159
159 31
31 15
15 7
7 5
336 340
340 342
342 86
86 22
22 6
870 871
871 359
359 103
103 39
39 7
141 13
13 9
...

result:

ok nice! 4775 moves

Test #11:

score: 0
Accepted
time: 0ms
memory: 3416kb

input:

1
819419 113088

output:

1
1 0

result:

ok nice! 1 moves

Test #12:

score: 0
Accepted
time: 0ms
memory: 3412kb

input:

2
725964 552203 371378 344109

output:

4
3 1
1 0
2 3
3 1

result:

ok nice! 4 moves

Test #13:

score: 0
Accepted
time: 1ms
memory: 3640kb

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:

7788
1023 511
511 255
255 127
127 63
63 31
31 15
15 7
7 3
3 1
1 0
1022 1023
1023 511
511 255
255 127
127 63
63 31
31 15
15 7
7 3
3 1
1021 1023
1023 511
511 255
255 127
127 63
63 31
31 15
15 7
7 3
3 2
1020 1022
1022 1023
1023 511
511 255
255 127
127 63
63 31
31 15
15 7
7 3
1019 1023
1023 511
511 255
...

result:

ok nice! 7788 moves

Test #14:

score: 0
Accepted
time: 0ms
memory: 3568kb

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:

7793
1023 511
511 255
255 127
127 63
63 31
31 15
15 7
7 3
3 1
1 0
1022 1023
1023 511
511 255
255 127
127 63
63 31
31 15
15 7
7 3
3 1
1021 1023
1023 511
511 255
255 127
127 63
63 31
31 15
15 7
7 3
3 2
1020 1022
1022 1023
1023 511
511 255
255 127
127 63
63 31
31 15
15 7
7 3
1019 1023
1023 511
511 255
...

result:

ok nice! 7793 moves

Test #15:

score: 0
Accepted
time: 2ms
memory: 3608kb

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:

7754
1023 511
511 255
255 127
127 63
63 31
31 15
15 7
7 3
3 1
1 0
1022 1023
1023 511
511 255
255 127
127 63
63 31
31 15
15 7
7 3
3 1
1021 1023
1023 511
511 255
255 127
127 63
63 31
31 15
15 7
7 3
3 2
1020 1022
1022 1023
1023 511
511 255
255 127
127 63
63 31
31 15
15 7
7 3
1019 1023
1023 511
511 255
...

result:

ok nice! 7754 moves

Test #16:

score: 0
Accepted
time: 0ms
memory: 3608kb

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:

6699
435 179
179 51
51 19
19 3
3 1
1 0
1022 1023
1023 511
511 255
255 127
127 63
63 31
31 15
15 7
7 3
3 1
1021 1023
1023 511
511 255
255 127
127 63
63 31
31 15
15 7
7 3
3 2
523 11
11 3
1019 1023
1023 511
511 255
255 127
127 63
63 31
31 15
15 7
7 5
5 4
1018 1022
1022 1023
1023 511
511 255
255 127
127...

result:

ok nice! 6699 moves

Test #17:

score: 0
Accepted
time: 2ms
memory: 3600kb

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:

6564
422 166
166 38
38 6
6 2
2 0
45 13
13 5
5 1
1021 1023
1023 511
511 255
255 127
127 63
63 31
31 15
15 7
7 3
3 2
1020 1022
1022 1023
1023 511
511 255
255 127
127 63
63 31
31 15
15 7
7 3
1019 1023
1023 511
511 255
255 127
127 63
63 31
31 15
15 7
7 5
5 4
1018 1022
1022 1023
1023 511
511 255
255 127
...

result:

ok nice! 6564 moves

Test #18:

score: 0
Accepted
time: 2ms
memory: 3544kb

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:

6309
250 122
122 58
58 26
26 10
10 2
2 0
477 221
221 93
93 29
29 13
13 5
5 1
508 510
510 254
254 126
126 62
62 30
30 14
14 6
6 2
195 67
67 3
1019 1023
1023 511
511 255
255 127
127 63
63 31
31 15
15 7
7 5
5 4
634 638
638 639
639 127
127 63
63 31
31 15
15 7
7 5
756 758
758 246
246 118
118 54
54 22
22 ...

result:

ok nice! 6309 moves

Test #19:

score: 0
Accepted
time: 1ms
memory: 3604kb

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:

6164
1023 511
511 255
255 127
127 63
63 31
31 15
15 7
7 3
3 1
1 0
604 605
605 93
93 29
29 13
13 5
5 1
1021 1023
1023 511
511 255
255 127
127 63
63 31
31 15
15 7
7 3
3 2
1020 1022
1022 1023
1023 511
511 255
255 127
127 63
63 31
31 15
15 7
7 3
1019 1023
1023 511
511 255
255 127
127 63
63 31
31 15
15 7...

result:

ok nice! 6164 moves

Test #20:

score: 0
Accepted
time: 1ms
memory: 3592kb

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:

5171
194 66
66 2
2 0
835 323
323 67
67 3
3 1
353 355
355 99
99 35
35 3
3 2
646 647
647 135
135 7
7 3
867 871
871 359
359 103
103 39
39 7
7 5
5 4
553 557
557 45
45 13
13 5
637 639
639 127
127 63
63 31
31 15
15 7
7 6
193 197
197 199
199 71
71 7
1015 1023
1023 511
511 255
255 127
127 63
63 31
31 15
15 ...

result:

ok nice! 5171 moves

Test #21:

score: 0
Accepted
time: 0ms
memory: 3656kb

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:

4944
644 132
132 4
4 0
516 517
517 5
5 1
922 410
410 154
154 26
26 10
10 2
110 111
111 47
47 15
15 7
7 3
357 101
101 37
37 5
5 4
998 999
999 487
487 231
231 103
103 39
39 7
7 5
985 989
989 991
991 479
479 223
223 95
95 31
31 15
15 7
7 6
554 558
558 559
559 47
47 15
15 7
645 653
653 141
141 13
13 9
9...

result:

ok nice! 4944 moves

Test #22:

score: 0
Accepted
time: 1ms
memory: 3540kb

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:

4786
105 41
41 9
9 1
1 0
696 697
697 185
185 57
57 25
25 9
9 1
203 75
75 11
11 3
3 2
19 3
968 972
972 460
460 204
204 76
76 12
12 4
830 831
831 319
319 63
63 31
31 15
15 7
7 5
660 662
662 150
150 22
22 6
747 751
751 239
239 111
111 47
47 15
15 7
464 472
472 216
216 88
88 24
24 8
570 571
571 59
59 27...

result:

ok nice! 4786 moves