QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#567113#1817. AND PermutationBakry#AC ✓3633ms486920kbC++142.0kb2024-09-16 07:20:382024-09-16 07:20:39

Judging History

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

  • [2024-09-16 07:20:39]
  • 评测
  • 测评结果:AC
  • 用时:3633ms
  • 内存:486920kb
  • [2024-09-16 07:20:38]
  • 提交

answer

#include <iostream>
#include <vector> 
#include <unordered_map>
#include <set>
#include <map>
#include <assert.h> 
using namespace std;
#define ll long long
std::pair<std::vector<long long>, std::vector<long long>>  solve(vector<ll>& arr, int x) {
    if (x < 0 || arr.size() == 0) {
        return { vector<ll>(arr.size(), 0), vector<ll>(arr.size(), 0) };
    }
    // find the values which have bit x set
    // cout << x << endl;
    // return { {}, {} };
    vector<ll> A, B;
    map<ll, ll> posB;
    for (int i = 0; i < arr.size(); i++) {
        if (arr[i] & (1ll << x)) {
            A.push_back(arr[i] ^ (1ll << x));
        }
        else {
            B.push_back(arr[i]);
            posB[arr[i] & ((1ll << x) - 1)] = i;
        }
    }
    // return { {}, {} };
    // set<int> all;
    auto [A1, A2] = solve(A, x - 1);
    auto [B1, B2] = solve(B, x - 1);
    set<ll> all;
    for (ll t : A1) {
        // all[t & ((1 << x) - 1)] = 0;
        all.insert(t);
    }

    // for (auto& t : A1) {
    //     t ^= (1 << x);
    // }
    for (long long& t : B1) {
        if (all.count(t)) {
            // assert(1 << x == 1ll << x);
            t ^= (1ll << x);
        }
    }
    // now for every B1 
    auto& res1 = A1;
    auto& res2 = A2;
    for (ll& t : res2)
        t ^= (1ll << x);

    for (int i = 0; i < B1.size(); i++) {
        res1.push_back(B1[i]);
        res2.push_back(B2[i]);
    }

    return { res1, res2 };
}

main() {
    int n;
    cin >> n;

    vector<ll> arr;
    unordered_map<ll, ll> mp;
    for (int i = 0; i < n; i++) {
        ll x; cin >> x;
        arr.push_back(x);
        mp[x] = i;

        // sort(arr.bsegin(), arr.end());
    }
    auto [A, B] = solve(arr, 59);
    // return 0;
    vector<ll> E(n);
    // cout << A.size() << ' ' << B.size() << ' ';
    for (int i = 0; i < arr.size(); i++) {

        E[mp[A[i]]] = B[i];
        // cout << mp[arr[i]];
    }
    for (int i = 0; i < n; i++) {
        cout << E[mp[arr[i]]] << '\n';
    }
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3664kb

input:

6
0
1
4
5
2
6

output:

6
4
2
0
5
1

result:

ok OK!

Test #2:

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

input:

272
315
138
126
6
394
297
44
273
84
200
9
197
396
133
16
46
65
87
86
336
316
174
140
162
250
306
52
188
57
36
63
192
320
388
10
156
15
208
38
32
31
228
30
305
234
384
220
142
72
27
337
110
94
317
304
242
398
209
5
323
29
284
301
309
244
230
261
61
254
266
194
296
275
313
80
206
214
88
308
18
288
106...

output:

4
309
129
416
116
22
275
198
170
55
310
58
114
82
323
273
318
128
168
174
195
81
307
285
5
204
267
67
262
394
256
63
190
122
388
98
304
47
392
398
288
27
289
14
21
126
35
305
182
292
140
145
160
2
206
13
112
46
314
148
290
226
18
10
11
25
210
258
1
244
61
215
196
6
303
49
41
166
202
321
222
149
281
...

result:

ok OK!

Test #3:

score: 0
Accepted
time: 51ms
memory: 20868kb

input:

5134
36416
73248
85220
2072
16524
36385
101507
91137
17604
22
640
70530
66850
107792
81952
163
84260
46246
45090
101411
18824
66360
116881
400
50338
109824
17508
122881
98691
99843
36481
1696
102658
27008
2566
4
32900
103171
1153
104706
69923
82280
19616
66849
17540
36870
8352
117777
82156
6785
6780...

output:

12326
33169
264
1094
69729
70018
4896
39842
67880
70657
105763
35873
39553
18572
46214
106240
1224
16385
17540
4992
66660
40966
9472
125953
12292
16620
67976
8098
7712
6560
69922
104707
3745
103971
8352
85480
29730
3232
125200
1697
36480
3204
70403
39568
67944
25760
54278
8576
4099
99618
17681
66562...

result:

ok OK!

Test #4:

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

input:

15
10
0
11
13
2
14
4
1
5
6
8
12
3
7
9

output:

5
14
4
2
13
1
11
12
10
9
7
3
8
0
6

result:

ok OK!

Test #5:

score: 0
Accepted
time: 27ms
memory: 14828kb

input:

3237
9776
12036
8229
2100
10676
17349
26144
2690
30256
3088
27328
31796
3344
54
3637
16908
17030
31749
8593
153
20020
2305
24980
17413
1155
16524
1068
16576
2881
1139
10416
1924
17284
1042
16969
1066
28084
24608
29220
25125
19744
26117
128
28724
4760
17792
27008
17696
4372
6784
19157
8577
405
19072
...

output:

22533
16593
24080
30209
17921
10288
6360
24589
2437
29221
4372
897
25285
1544
28672
10370
10248
976
19012
1122
12289
25300
4160
14896
120
10754
530
11060
24724
136
18180
26705
11313
556
8196
533
522
7701
3472
7184
8853
6192
28468
3968
2144
10837
1598
10901
20128
1332
8448
19028
27200
9524
16533
8469...

result:

ok OK!

Test #6:

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

input:

32
21
10
13
29
15
30
14
0
26
19
18
2
8
25
5
23
17
12
24
3
4
22
20
27
6
9
1
28
7
16
11
31

output:

10
21
18
2
16
1
17
31
5
12
13
29
23
6
26
8
14
19
7
28
27
9
11
4
25
22
30
3
24
15
20
0

result:

ok OK!

Test #7:

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

input:

286
304
63
445
257
143
170
407
68
55
44
256
53
176
310
4
436
356
33
6
442
160
38
314
273
296
420
299
173
64
408
0
401
169
423
40
284
135
187
358
397
301
70
260
393
190
174
36
428
65
183
421
21
390
58
28
73
288
434
403
104
10
405
443
168
46
43
171
47
398
311
185
279
413
15
277
23
19
20
42
261
278
139...

output:

143
384
2
190
304
277
40
315
392
403
191
394
271
137
443
11
27
414
441
5
326
409
133
174
151
66
148
274
319
102
447
104
278
24
407
163
312
260
25
50
146
313
187
112
257
273
411
19
62
264
26
426
97
389
419
54
159
13
44
23
437
42
4
279
401
404
276
400
49
136
262
168
34
432
170
424
428
427
405
186
169
...

result:

ok OK!

Test #8:

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

input:

260
261
790
778
536
273
7
28
19
840
12
3
527
75
4
599
795
336
543
793
82
850
286
852
2
848
539
841
587
847
326
535
515
519
837
86
78
322
271
525
80
785
22
596
523
794
95
81
339
70
798
590
67
333
69
834
284
21
540
30
72
789
581
514
8
26
27
11
1024
594
770
257
348
279
861
331
73
600
264
277
577
6
345
...

output:

602
73
85
327
590
856
835
844
23
851
860
336
788
859
264
68
527
320
70
781
13
577
11
861
15
324
22
276
16
537
328
348
344
26
777
785
541
592
338
783
78
841
267
340
69
768
782
524
793
65
273
796
530
794
29
579
842
323
833
791
74
282
349
1025
837
836
852
863
269
93
606
515
584
2
532
790
263
599
586
28...

result:

ok OK!

Test #9:

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

input:

128
240
194
178
243
2
131
163
32
112
225
153
129
97
82
25
158
140
144
134
66
69
65
98
24
13
26
192
157
160
3
49
211
196
6
133
14
33
5
12
139
99
176
28
179
83
138
11
150
19
155
224
137
208
15
4
154
113
143
147
135
18
81
34
149
73
136
23
76
209
30
197
146
27
17
80
48
227
145
168
152
68
0
50
1
51
29
20...

output:

15
49
65
12
241
112
80
211
143
30
6
114
158
168
134
1
67
99
25
177
154
178
157
135
194
133
51
2
83
240
204
32
27
153
72
145
210
200
195
20
156
77
131
64
160
33
148
9
224
4
31
68
42
144
201
5
142
16
96
24
225
162
209
10
150
69
136
147
34
129
26
97
132
226
170
205
28
98
23
7
155
243
193
242
192
130
13...

result:

ok OK!

Test #10:

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

input:

24
2
12
28
5
26
3
24
10
8
7
22
17
1
6
16
20
19
0
18
11
4
9
25
27

output:

25
19
3
2
5
24
7
20
22
0
1
10
26
17
12
11
8
28
9
16
27
18
6
4

result:

ok OK!

Test #11:

score: 0
Accepted
time: 10ms
memory: 9564kb

input:

1572
2144
58
3077
672
2376
2112
3978
1879
1170
557
2817
851
3975
2346
1814
1294
24
2602
1610
3457
606
1875
2818
2629
864
2156
1350
178
30
674
1547
2668
2948
1864
2432
2178
1310
176
2317
658
1057
587
2152
256
2927
1069
1282
1682
440
2208
2096
2850
1213
3076
3599
2607
1574
849
657
1188
578
676
1161
11...

output:

799
2240
906
3094
1559
1840
116
8
2605
2370
1212
1036
104
597
201
2689
2274
341
293
624
1281
12
1205
1306
2202
787
561
3597
1857
3092
2436
275
1115
182
1631
1885
577
3599
1666
3108
862
2340
791
3766
16
850
2740
2157
71
1567
1807
220
2
907
384
336
2377
1068
1358
2635
2349
3090
2918
2913
2702
2945
141...

result:

ok OK!

Test #12:

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

input:

494
410
96
93
915
349
71
374
344
537
649
146
962
132
19
78
141
162
103
101
272
263
2
367
615
544
787
898
368
70
994
15
185
355
594
113
80
61
326
60
576
200
612
385
586
154
5
657
520
319
528
58
271
194
274
290
377
369
9
769
362
125
614
50
102
651
393
74
371
810
682
375
519
583
98
64
119
387
424
391
3...

output:

613
923
290
108
34
544
9
39
390
374
777
61
379
904
305
370
840
512
514
651
128
1000
16
280
461
168
125
15
545
29
368
70
28
301
270
554
322
57
323
426
802
283
614
416
769
610
366
482
64
397
581
112
808
649
712
6
14
914
204
657
258
281
584
513
372
530
928
12
193
341
8
384
312
921
938
264
612
594
120
1...

result:

ok OK!

Test #13:

score: 0
Accepted
time: 3523ms
memory: 486528kb

input:

199969
8669248
1075841048
201328650
44042242
577154
1477480448
75844
406986886
1209534848
37758482
402981064
8462848
67126848
36160
35783200
268500996
25297024
203492360
138412736
1243643904
180232
570441730
272732160
67568128
52564512
570886432
34016
1225073920
536940936
1074372864
4556832
26850128...

output:

2294304
336593156
570426448
5768512
368
100943872
536905216
530448
263772
65804
49670
1077971328
272630168
142622856
541138968
1698693248
1079051312
1073762948
67141936
562364418
1610623616
420675584
202385920
151046144
4262164
3149900
4456476
8409320
16916544
134240320
8520730
1141638144
603982336
...

result:

ok OK!

Test #14:

score: 0
Accepted
time: 3110ms
memory: 452356kb

input:

190281
53740576
202441232
536983640
1145053184
202703424
706479124
537213456
135726400
322181124
369160232
264208
16875750
536984090
604439104
254017728
538217476
672404500
12716036
1075089440
401830
310411820
1357398048
201721088
151389008
67162128
302098580
385933344
310487132
134481938
1144115456...

output:

1879087108
554042720
402915842
708067532
553780528
4330274
402686026
620757552
1610646560
25166916
939635274
4596480
402915392
152044848
537944100
1394610208
38404616
539038514
857738244
21070400
75984
538065156
554762864
605094944
1215374592
8389224
8395542
674
805417544
138422308
537071648
1355366...

result:

ok OK!

Test #15:

score: 0
Accepted
time: 3633ms
memory: 486920kb

input:

199998
344064132
2066
301989920
83886244
1744994560
84017920
704909320
1090847234
1354825984
19407360
42205408
436469796
67963392
34621480
35652096
100673568
34734336
285356032
136316320
536912388
50667520
9199616
2099392
2621792
285220880
1182088
1581074
50320
17111168
67747856
20987920
672661780
1...

output:

35749920
1744830472
1291845698
142643202
343998592
35717268
84018178
8552576
137404448
538185988
16924700
75628562
181504
4457988
1615855872
1077969424
1090850824
142706824
1081428
270536960
71439392
16947200
1075576880
538050584
1217396744
557154
1073877000
4206914
1082690
134232072
1612720128
3933...

result:

ok OK!

Test #16:

score: 0
Accepted
time: 2236ms
memory: 177016kb

input:

199984
4402408632320
9034687045437440
18155138279542816
2269533733650432
9077568067863552
45176733762093056
4503668347109380
68719501312
563500280252416
10133374039506944
567382359670784
4329570308
144255925568405504
848827271610432
288233124932880384
162411061562179648
108086700294537232
2199137340...

output:

8796093025536
4674266595584
1130297953419280
18296526321221632
144115188075987600
20345363185532960
2533274790920192
108086391056926344
281474976751616
4785212118532096
36046597510922336
4504149383577600
81068160580583424
1125919238390272
18014400658031104
4538921706849280
20266748095759360
90194837...

result:

ok OK!

Test #17:

score: 0
Accepted
time: 1461ms
memory: 97724kb

input:

175134
108086408238334020
144115773533585824
72058968499306884
2533755843543040
146828920228937728
9007199254873088
218459768464475136
585474548627931136
281492160856100
2432326030065664
1460168630026244
2286997087993924
657811695644704776
146649631097389056
594479548859424768
2287544695799808
36029...

output:

9592173800460296
576465150383572992
36591747375038464
144296607628657152
1443243262464
432416002299400592
1099520278672
108368143092563976
1178676741800960
144398037442134528
272630816
9148488646656000
36030996075790336
180732374811136
72057595783351560
9147941038850116
72620819339559040
21620796863...

result:

ok OK!

Test #18:

score: 0
Accepted
time: 2301ms
memory: 236228kb

input:

198623
17188785152
687750512640
70403108110912
4471062004740
8590526656
35184372097280
1125901047694464
105561706332160
2201206521856
4399205466112
140737926660112
2815377939628040
309287979136
211123412402176
166912
422212465131688
569547159506984
1161153003683904
3377699787702272
79440788857120
70...

output:

142386755797160
4400202457344
36283901562880
2185232448
1099780096512
87965800087680
17695407865872
10995200230528
4362102272
35253095759952
4398050707460
4398113628672
536944672
2286994957271696
8796102787080
35467839932416
281474980905024
34361836560
573953676543104
35184406691848
1099511634048
67...

result:

ok OK!

Test #19:

score: 0
Accepted
time: 2783ms
memory: 306940kb

input:

199906
137438955040
23090817991168
139787763728
22541064208400
1236950606384
71468256591872
1099516354560
134480416
4400261120514
6597069864960
84021504
68720590856
2203318239234
8615116800
17729910226944
68753162498
9668003908
137440596000
35193029263360
6597069767756
27487808618626
79182017075232
...

output:

94497734656
8598364352
34393820192
2952792074
4398046515208
4952105762880
17596749512704
146029019272
2748781166600
9895622475906
69793267776
17593394003984
343615213568
9637906612288
35734128169088
4296278048
137447342082
4402341480960
17596482093058
549898420224
21536
9663938696
2199157610504
1036...

result:

ok OK!