QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#567112 | #1817. AND Permutation | Bakry# | WA | 3374ms | 487108kb | C++14 | 2.0kb | 2024-09-16 07:20:12 | 2024-09-16 07:20:14 |
Judging History
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 ^= (1 << 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: 3820kb
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: 4988kb
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: 37ms
memory: 20636kb
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: 0ms
memory: 3688kb
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: 26ms
memory: 14796kb
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: 3768kb
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: 2ms
memory: 5076kb
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: 4704kb
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: 4380kb
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: 3680kb
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: 9508kb
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: 3ms
memory: 5756kb
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: 3374ms
memory: 486560kb
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: 2937ms
memory: 452280kb
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: 3363ms
memory: 487108kb
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: -100
Wrong Answer
time: 2234ms
memory: 177148kb
input:
199984 4402408632320 9034687045437440 18155138279542816 2269533733650432 9077568067863552 45176733762093056 4503668347109380 68719501312 563500280252416 10133374039506944 567382359670784 4329570308 144255925568405504 848827271610432 288233124932880384 162411061562179648 108086700294537232 2199137340...
output:
1280 1342178624 328720 4259992 33686160 29902880 65536 25200264 106496 76611616 -2139090864 1441920 52429584 -2143026684 -2142223872 269493280 21496960 524373 35652120 34080962 2 135405568 15730720 34078768 100663872 139211008 138412032 43001856 34603072 2192 -1879047679 136317196 805306752 50336064...
result:
wrong answer Output value not an unused input value.