QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #410422 | #5053. Random Shuffle | Baiyu0123 | AC ✓ | 408ms | 7764kb | C++14 | 2.3kb | 2024-05-13 23:32:30 | 2024-05-13 23:32:30 |
Judging History
answer
#include<bits/stdc++.h>
#define ull unsigned long long
#define fi first
#define se second
#define mkp make_pair
using namespace std;
const int maxn=1e5+100;
ull S[64],T[64];
int n;
int a[maxn],w[maxn],rd[maxn];
void output(ull S) {
for (int j=0;j<64;j++) {
if (S&1ull<<j) cout<<j<<" ";
}
cout<<endl;
}
void move_to_left(int x) {
for (int i=0;i<64;i++) {
if (i-x>=0&&i-x<64) T[i]=S[i]^S[i-x];
else T[i]=S[i];
}
for (int i=0;i<64;i++) {
S[i]=T[i];
}
}
void Rand() {
move_to_left(13);
move_to_left(-7);
move_to_left(17);
}
pair<ull,int> Q[maxn],P[maxn];int pw=0;
void add(ull S,int x) {
P[pw++]=mkp(S,x);
}
bool check(ull ans) {
for (int i=1;i<=n;i++) {
ans^=ans<<13;
ans^=ans>>7;
ans^=ans<<17;
if (rd[i]!=(ans%i)) return 0;
}
return 1;
}
void calc() {
int st=0;
for (int i=0;i<64;i++) {
if (!(P[st].fi&(1ull<<i))) {
for (int j=st+1;j<pw;j++) {
if (P[j].fi&(1ull<<i)) {
swap(P[st],P[j]);
break;
}
}
}
if (!(P[i].fi&(1ull<<i))) {
continue;
}
//assert(P[i].fi&(1ull<<i));
for (int j=0;j<pw;j++) {
if (st==j||!(P[j].fi&(1ull<<i))) continue;
P[j].fi^=P[st].fi;
P[j].se^=P[st].se;
}
st++;
}
for (int i=0;i<st;i++) Q[i]=P[i];
for (ull S=0;S<(1ull<<(64-st));S++) {
for (int i=0;i<st;i++) P[i]=Q[i];
for (int i=0;st+i<64;i++) {
P[st+i]=mkp(1ull<<(st+i),(S&1ull<<i)>>i/*(16659580358178468547ull&1ull<<(st+i))>>(st+i)*/);
for (int j=0;j<st;j++) {
if (P[j].fi&(1ull<<(st+i))) {
P[j].fi^=P[st+i].fi;
P[j].se^=P[st+i].se;
}
}
}
ull ans=0;
for (int i=0;i<64;i++) {
// cout<<i<<" "<<P[i].se<<" : ";
// output(P[i].fi);
// assert(P[i].fi==(1ull<<i));
ans|=(1ull*P[i].se)<<i;
}
if (check(ans)) {
cout<<ans<<endl;
return ;
}
}
}
int main() {
cin>>n;
for (int i=1;i<=n;i++) cin>>a[i],w[a[i]]=i;
for (int i=n;i>=1;i--) {
w[a[i]]=w[i];
rd[i]=w[i]-1;
swap(a[i],a[w[i]]);
}
for (int i=0;i<64;i++) S[i]=1ull<<i;
for (int i=1;i<=50;i++) {
Rand();
if (i%2==0) {
for (int j=0;!(i&1<<j);j++) {
// cout<<i<<" "<<j<<endl;
add(S[j],(rd[i]&(1<<j))>>(j));
}
}
}
calc();
//cout<<check(16659580358178468547ull)<<endl;
//cout<<pw<<endl;
//Rand();Rand();
//output();
}
詳細信息
Test #1:
score: 100
Accepted
time: 361ms
memory: 5664kb
input:
50 36 22 24 21 27 50 28 14 25 34 18 43 47 13 30 7 10 48 20 16 29 9 8 15 3 31 12 38 19 49 37 1 46 32 4 44 11 35 6 33 26 5 45 17 39 40 2 23 42 41
output:
16659580358178468547
result:
ok OK, Accepted.
Test #2:
score: 0
Accepted
time: 37ms
memory: 5652kb
input:
50 26 36 12 27 8 1 33 17 16 48 11 22 20 10 23 47 5 32 35 21 31 49 45 43 29 2 13 41 4 6 3 50 30 7 9 15 14 38 25 46 28 37 39 18 42 24 19 40 44 34
output:
1881993639894066979
result:
ok OK, Accepted.
Test #3:
score: 0
Accepted
time: 118ms
memory: 5552kb
input:
50 40 28 8 31 5 15 16 26 29 12 22 45 11 32 25 21 35 9 24 3 4 23 36 6 41 44 27 48 34 49 37 13 33 39 10 17 2 46 42 18 7 14 50 20 47 30 1 38 19 43
output:
5551150991024249731
result:
ok OK, Accepted.
Test #4:
score: 0
Accepted
time: 197ms
memory: 5552kb
input:
50 47 35 20 16 14 21 32 40 38 37 43 27 45 22 5 13 4 36 33 2 19 31 11 46 39 29 48 18 1 9 42 44 23 12 49 41 3 50 28 6 10 8 25 30 15 24 7 17 26 34
output:
9220308350744367075
result:
ok OK, Accepted.
Test #5:
score: 0
Accepted
time: 275ms
memory: 5592kb
input:
50 32 7 36 49 35 21 15 27 16 41 4 10 25 34 24 40 17 9 45 30 12 11 20 2 31 19 3 39 14 8 38 18 47 33 50 37 48 46 43 22 42 29 23 13 1 5 26 28 44 6
output:
12889465701874549827
result:
ok OK, Accepted.
Test #6:
score: 0
Accepted
time: 352ms
memory: 5652kb
input:
50 4 11 21 1 46 26 43 2 31 27 41 38 29 37 40 3 33 34 18 50 39 42 8 17 47 32 49 15 35 13 28 45 6 7 20 16 23 10 22 5 36 25 12 9 19 14 48 30 44 24
output:
16558623053004732579
result:
ok OK, Accepted.
Test #7:
score: 0
Accepted
time: 35ms
memory: 5748kb
input:
50 7 11 31 6 24 40 18 17 25 20 43 26 1 44 15 4 32 47 10 12 34 16 14 36 46 42 13 27 33 3 30 23 39 5 50 45 8 35 21 19 49 41 38 37 9 2 29 48 22 28
output:
1781036334720331011
result:
ok OK, Accepted.
Test #8:
score: 0
Accepted
time: 116ms
memory: 5752kb
input:
50 23 42 40 19 49 37 11 22 29 14 8 36 13 26 18 7 31 10 15 16 21 30 41 43 48 20 6 2 3 4 5 50 45 33 32 38 25 9 44 27 35 46 12 39 28 17 1 24 34 47
output:
5450193690145481059
result:
ok OK, Accepted.
Test #9:
score: 0
Accepted
time: 190ms
memory: 5688kb
input:
50 27 25 38 11 26 45 5 48 12 37 46 42 39 4 7 31 41 33 29 35 20 23 49 50 14 3 16 17 47 34 21 44 18 8 9 30 6 24 43 19 36 15 1 40 22 13 28 2 10 32
output:
9119351041275663811
result:
ok OK, Accepted.
Test #10:
score: 0
Accepted
time: 298ms
memory: 7764kb
input:
50 11 10 48 50 40 1 44 13 33 23 21 3 24 5 31 15 37 43 7 26 12 28 42 45 29 6 27 25 20 8 17 34 46 39 2 36 18 47 22 16 14 19 35 32 9 30 38 41 49 4
output:
14147710490869904115
result:
ok OK, Accepted.
Test #11:
score: 0
Accepted
time: 70ms
memory: 5676kb
input:
60 18 36 13 59 56 4 17 15 8 32 14 16 9 53 38 48 60 21 49 24 27 19 40 45 20 25 22 55 37 43 39 57 34 46 54 30 35 10 26 29 7 44 2 51 11 3 58 28 31 12 1 47 41 33 42 23 6 5 52 50
output:
3245388184900135407
result:
ok OK, Accepted.
Test #12:
score: 0
Accepted
time: 148ms
memory: 7704kb
input:
60 2 10 59 47 20 25 7 55 56 57 13 1 50 40 43 4 15 42 38 31 49 39 11 28 41 30 23 16 54 27 52 26 51 17 44 46 19 3 32 24 45 21 60 33 9 34 8 48 5 12 37 22 14 35 58 36 6 18 53 29
output:
6914545536030318160
result:
ok OK, Accepted.
Test #13:
score: 0
Accepted
time: 227ms
memory: 5688kb
input:
60 55 16 11 49 43 6 20 19 54 40 35 5 22 45 14 17 44 9 48 27 56 59 2 18 4 34 58 31 36 1 24 47 26 52 15 13 41 32 12 37 29 30 53 33 7 50 38 28 57 60 21 23 10 3 39 42 8 46 51 25
output:
10583702891455468208
result:
ok OK, Accepted.
Test #14:
score: 0
Accepted
time: 299ms
memory: 5660kb
input:
60 35 23 13 59 8 30 10 18 3 36 60 56 54 1 6 58 20 21 11 16 53 4 33 19 44 27 22 14 39 31 32 45 57 15 25 28 7 50 9 24 52 34 26 43 5 47 42 49 51 37 17 12 41 48 29 55 38 2 40 46
output:
14252860242585650960
result:
ok OK, Accepted.
Test #15:
score: 0
Accepted
time: 383ms
memory: 5748kb
input:
60 48 60 34 7 41 15 53 37 39 9 42 36 31 20 40 22 33 24 16 46 30 6 26 35 12 10 58 55 23 27 14 49 28 56 3 1 11 2 25 19 8 29 50 13 32 38 52 44 18 47 43 51 5 17 4 57 59 54 45 21
output:
17922017602305768304
result:
ok OK, Accepted.
Test #16:
score: 0
Accepted
time: 178ms
memory: 5748kb
input:
70 20 19 56 69 43 3 47 37 66 6 1 40 53 57 55 39 70 32 24 61 21 33 12 10 31 28 11 65 30 18 63 68 4 26 34 16 46 17 9 52 7 62 15 36 38 67 8 35 41 5 60 25 50 42 23 22 27 48 58 45 14 64 13 44 59 49 54 51 29 2
output:
8277940081036386588
result:
ok OK, Accepted.
Test #17:
score: 0
Accepted
time: 254ms
memory: 5736kb
input:
70 48 47 31 34 22 6 29 21 33 7 49 66 55 9 41 68 5 17 63 19 15 52 26 32 61 70 16 44 13 37 50 3 38 20 60 67 51 40 42 35 56 11 65 58 4 53 43 2 30 57 39 27 23 69 59 1 18 36 10 12 54 62 24 64 45 25 28 8 46 14
output:
11947097436461536636
result:
ok OK, Accepted.
Test #18:
score: 0
Accepted
time: 332ms
memory: 5604kb
input:
70 53 47 50 9 68 1 39 36 44 27 38 16 6 45 49 64 54 63 35 67 41 60 19 37 48 10 29 20 30 59 25 56 46 42 26 17 18 31 13 8 5 4 57 62 55 21 12 2 24 23 40 15 32 52 34 51 61 43 11 33 58 3 22 66 7 70 28 69 65 14
output:
15616254791886686684
result:
ok OK, Accepted.
Test #19:
score: 0
Accepted
time: 18ms
memory: 5716kb
input:
70 20 16 4 42 10 54 9 36 67 30 3 7 52 33 59 57 17 1 32 56 60 24 5 65 23 55 69 63 39 31 46 68 35 21 18 15 51 6 45 41 25 70 66 40 34 44 19 53 61 2 49 58 64 11 38 48 27 62 12 43 22 29 13 14 26 8 50 28 47 37
output:
838668069307317820
result:
ok OK, Accepted.
Test #20:
score: 0
Accepted
time: 96ms
memory: 5672kb
input:
70 68 33 21 22 7 12 6 27 57 60 69 49 48 53 70 20 59 43 54 24 14 10 25 30 52 45 11 63 40 46 41 28 65 56 29 64 9 47 61 23 1 58 34 38 13 8 31 32 19 35 2 67 3 51 5 66 17 42 18 62 16 36 55 26 44 37 39 50 4 15
output:
4507825420437500572
result:
ok OK, Accepted.
Test #21:
score: 0
Accepted
time: 285ms
memory: 5692kb
input:
80 49 39 52 59 15 5 74 56 78 50 18 3 19 1 2 30 76 10 28 43 36 26 57 23 35 34 8 48 65 4 22 79 58 37 17 20 45 11 32 6 47 38 71 80 41 60 13 75 12 24 66 70 77 16 25 54 55 61 69 53 29 9 42 68 46 62 14 72 73 21 63 44 7 31 67 64 51 33 40 27
output:
13310491977172637768
result:
ok OK, Accepted.
Test #22:
score: 0
Accepted
time: 363ms
memory: 5668kb
input:
80 56 67 36 42 52 73 38 18 80 9 2 62 5 54 59 33 16 37 66 75 71 61 17 20 57 60 19 1 64 27 58 51 6 39 49 34 7 32 69 65 45 24 48 79 21 31 12 11 22 30 26 72 35 63 47 68 77 74 70 53 8 43 25 14 13 41 78 76 23 3 44 55 10 28 50 4 29 46 40 15
output:
16979649332597787816
result:
ok OK, Accepted.
Test #23:
score: 0
Accepted
time: 47ms
memory: 5748kb
input:
80 8 12 3 46 21 72 73 15 50 32 47 39 31 45 55 63 62 76 23 34 18 68 48 40 30 80 60 78 51 75 43 61 42 9 35 16 79 74 10 70 58 4 44 56 1 65 14 20 28 11 36 7 5 19 17 77 54 2 53 52 37 64 29 49 33 6 67 26 27 22 66 24 41 57 59 71 13 38 69 25
output:
2202062614313386248
result:
ok OK, Accepted.
Test #24:
score: 0
Accepted
time: 125ms
memory: 5668kb
input:
80 74 23 25 41 38 69 42 2 33 76 19 54 8 70 37 34 40 46 72 27 75 80 3 64 57 78 67 79 20 36 21 50 71 11 62 9 12 15 73 65 43 63 51 49 16 59 35 28 77 22 61 10 45 18 24 26 56 7 13 14 30 32 44 4 55 58 31 1 68 6 53 5 52 39 66 60 47 29 17 48
output:
5871219969738536296
result:
ok OK, Accepted.
Test #25:
score: 0
Accepted
time: 199ms
memory: 5548kb
input:
80 50 4 28 18 51 23 16 5 39 59 1 56 44 19 45 75 20 21 26 41 42 24 38 3 9 15 62 77 53 35 72 12 73 29 64 7 30 74 6 76 67 55 49 52 8 27 22 11 68 47 70 37 34 31 17 10 78 57 48 13 36 25 71 58 43 14 60 66 65 46 40 32 63 54 80 33 79 69 2 61
output:
9540377320868719048
result:
ok OK, Accepted.
Test #26:
score: 0
Accepted
time: 200ms
memory: 5688kb
input:
100 93 100 16 35 18 69 77 90 89 94 4 51 87 29 59 64 79 22 38 19 46 45 58 61 82 73 66 99 26 44 41 15 55 57 85 49 53 32 13 56 74 54 8 71 88 36 60 91 12 98 43 83 37 67 75 92 31 30 39 81 97 95 65 23 52 5 48 50 34 70 76 28 25 27 14 20 80 47 2 10 17 84 9 7 1 33 3 63 40 24 68 96 21 86 6 11 62 42 78 72
output:
9372034917709956260
result:
ok OK, Accepted.
Test #27:
score: 0
Accepted
time: 279ms
memory: 5736kb
input:
100 54 21 13 36 48 88 75 67 23 27 37 20 89 77 6 55 79 73 12 4 57 86 15 24 74 62 68 19 2 97 10 78 76 44 61 58 34 83 43 84 93 3 96 22 8 16 14 71 41 64 49 39 32 47 70 42 82 60 66 38 87 1 17 51 40 18 7 81 59 80 31 91 63 85 92 25 35 29 90 9 5 33 50 72 65 69 26 95 100 46 30 45 11 53 56 99 94 98 52 28
output:
13041192273135106308
result:
ok OK, Accepted.
Test #28:
score: 0
Accepted
time: 351ms
memory: 5592kb
input:
100 64 80 14 61 43 54 28 79 77 24 21 38 60 94 56 22 62 12 69 7 71 75 98 52 59 68 34 58 44 39 97 73 53 92 25 50 76 85 4 30 31 47 90 10 18 19 33 96 1 72 83 35 23 8 15 84 29 48 49 41 82 11 88 40 42 70 65 27 93 13 78 51 99 45 17 32 91 20 3 36 55 6 87 26 63 5 46 57 67 95 74 16 9 100 81 66 2 86 89 37
output:
16710349624265289060
result:
ok OK, Accepted.
Test #29:
score: 0
Accepted
time: 42ms
memory: 5672kb
input:
100 72 82 64 37 50 85 34 59 11 80 66 9 69 79 77 61 15 41 63 26 56 94 42 33 27 30 40 20 68 97 45 6 29 96 78 18 19 67 44 75 95 16 98 54 87 35 53 23 39 31 21 100 43 60 48 2 99 3 93 46 10 8 13 73 76 7 71 70 25 81 58 88 65 89 5 91 55 84 24 22 47 36 49 4 62 83 14 32 17 74 57 92 52 12 38 90 51 86 28 1
output:
1932762905980887492
result:
ok OK, Accepted.
Test #30:
score: 0
Accepted
time: 119ms
memory: 5664kb
input:
100 92 55 24 33 80 68 34 89 15 39 93 60 99 51 86 16 37 49 22 57 100 38 41 45 28 4 17 20 64 21 1 5 96 90 77 2 65 26 9 23 50 79 44 48 43 3 81 12 91 35 27 25 71 67 6 62 52 78 72 7 42 8 87 32 40 58 53 19 13 69 76 61 97 59 70 46 74 63 98 83 47 31 54 29 10 95 18 11 88 85 30 36 66 82 84 73 75 56 14 94
output:
5601920257111070244
result:
ok OK, Accepted.
Test #31:
score: 0
Accepted
time: 35ms
memory: 5700kb
input:
1000 14 801 876 665 517 379 816 862 669 636 471 806 50 113 293 652 585 758 594 919 282 532 916 870 899 91 456 844 562 223 428 656 951 760 396 653 744 435 486 887 449 591 599 923 557 582 507 197 691 476 464 759 244 114 73 419 327 209 96 846 785 828 206 674 742 895 37 549 296 482 275 286 918 498 529 4...
output:
1601957447185507124
result:
ok OK, Accepted.
Test #32:
score: 0
Accepted
time: 163ms
memory: 5592kb
input:
10000 8488 3752 5772 3495 4540 2525 85 9115 7674 2753 4345 8859 1164 8515 2278 350 3632 8316 1394 172 6352 4168 2775 2069 5236 4146 6692 6925 1222 8341 9455 5785 5998 2579 6458 6397 4043 8563 7633 8348 3622 2802 4558 2911 747 1948 9329 3778 4803 6478 1590 7643 3099 9004 4528 4737 5941 991 9689 256 1...
output:
7604483965017321570
result:
ok OK, Accepted.
Test #33:
score: 0
Accepted
time: 399ms
memory: 6260kb
input:
100000 98458 53652 83234 44212 86777 91201 40842 73330 10976 49792 61331 57415 7021 96999 69196 44608 39826 16934 50858 33904 31103 58699 29546 91218 96992 71234 42816 81918 80692 97038 9396 73201 18264 46062 44975 86005 7196 6985 62915 36202 49770 7636 53980 9029 11019 43660 52488 48199 57296 75879...
output:
17967841127598789655
result:
ok OK, Accepted.
Test #34:
score: 0
Accepted
time: 0ms
memory: 5668kb
input:
50 50 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
output:
0
result:
ok OK, Accepted.
Test #35:
score: 0
Accepted
time: 189ms
memory: 5668kb
input:
50 12 40 24 22 39 50 32 26 41 8 38 48 28 49 42 45 44 23 5 16 36 2 9 37 10 15 34 18 20 1 31 13 14 3 30 33 21 29 43 35 27 17 6 47 4 19 46 25 7 11
output:
9223372036854775808
result:
ok OK, Accepted.
Test #36:
score: 0
Accepted
time: 256ms
memory: 5540kb
input:
50 17 20 40 34 43 21 45 13 25 7 41 29 33 12 6 26 37 3 32 22 5 11 44 47 42 36 15 28 39 49 4 19 35 8 16 24 48 50 14 10 30 1 31 9 2 23 27 18 46 38
output:
12223372036854775808
result:
ok OK, Accepted.
Test #37:
score: 0
Accepted
time: 388ms
memory: 5564kb
input:
50 47 14 37 36 43 2 34 26 48 6 45 11 27 22 9 42 4 13 33 46 18 25 12 19 32 49 8 40 15 7 1 29 44 24 20 17 30 50 16 35 39 21 28 41 10 23 3 5 38 31
output:
18446744073709551615
result:
ok OK, Accepted.
Test #38:
score: 0
Accepted
time: 14ms
memory: 6816kb
input:
100000 100000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...
output:
0
result:
ok OK, Accepted.
Test #39:
score: 0
Accepted
time: 213ms
memory: 6772kb
input:
100000 82839 4570 40007 26592 17582 28077 42446 30175 13415 28222 96521 15740 56356 51662 82159 6782 82291 29178 45576 71513 64489 91101 70728 8178 32839 74729 95237 27071 61633 57277 64820 17785 95449 64837 85431 15345 56582 36978 99174 8077 79117 36083 39017 5834 95122 90789 34914 8247 46269 67980...
output:
9223372036854775808
result:
ok OK, Accepted.
Test #40:
score: 0
Accepted
time: 408ms
memory: 6440kb
input:
100000 19820 98878 59554 94113 95501 298 26997 41493 74443 19973 63466 98813 7604 44016 82921 94828 20071 25852 65754 67895 93811 37520 60312 81459 8312 40128 3165 65671 75422 35088 19340 26620 88752 99203 69553 10735 62787 72679 49099 22739 6613 67938 44453 51384 23070 983 88383 49704 32724 95008 4...
output:
18446744073709551615
result:
ok OK, Accepted.