QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #456204 | #5053. Random Shuffle | zyz07 | AC ✓ | 40ms | 4840kb | C++17 | 1.8kb | 2024-06-27 13:37:27 | 2024-06-27 13:37:28 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define For(Ti,Ta,Tb) for(auto Ti=(Ta);Ti<=(Tb);++Ti)
#define Dec(Ti,Ta,Tb) for(auto Ti=(Ta);Ti>=(Tb);--Ti)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define range(Tx) begin(Tx),end(Tx)
using ll=long long;
using ull=unsigned long long;
ull f(ull x){
x^=x<<13;
x^=x>>7;
x^=x<<17;
return x;
}
const int N=1e5+5;
int n,a[N],pos[N],mod[N];
struct Basis{
ull x[64];
bool v[64];
bool insert(ull x_,bool v_){
Dec(i,63,0){
if(!(x_>>i&1)) continue;
if(!x[i]){
x[i]=x_;
v[i]=v_;
Dec(j,i-1,0){
if(x[i]>>j&1){
x[i]^=x[j];
v[i]^=v[j];
}
}
For(j,i+1,63){
if(x[j]>>i&1){
x[j]^=x[i];
v[j]^=v[i];
}
}
return 1;
}
x_^=x[i];
v_^=v[i];
}
assert(!x_&&!v_);
return 0;
}
}base;
ull val[64];
void dfs(int u){
if(u==64){
ull ans=0;
For(i,0,63){
ans|=ull(base.v[i])<<i;
}
bool flg=1;
ull x=ans;
For(i,1,n){
x=f(x);
if(int(x%i)!=mod[i]){
flg=0;
break;
}
}
if(flg){
cout<<ans<<'\n';
exit(0);
}
return;
}
if(base.x[u]){
dfs(u+1);
}else{
Basis base_{base};
For(x,0,1){
base.insert(1LLU<<u,x);
dfs(u+1);
base=base_;
}
}
}
int main(){
cin.tie(nullptr)->sync_with_stdio(false);
cin>>n;
For(i,1,n){
cin>>a[i];
pos[a[i]]=i;
}
Dec(i,n,1){
mod[i]=pos[i]-1;
swap(a[pos[i]],a[i]);
swap(pos[i],pos[a[pos[i]]]);
}
For(i,0,63){
val[i]=1LLU<<i;
}
int tot=0;
For(i,1,n){
For(j,0,63){
val[j]=f(val[j]);
}
For(j,0,int(__builtin_ctz(i))-1){
ull x=0;
For(k,0,63){
if(val[k]>>j&1){
x|=1LLU<<k;
}
}
tot+=base.insert(x,mod[i]>>j&1);
}
}
dfs(0);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 25ms
memory: 3576kb
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: 26ms
memory: 3620kb
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: 25ms
memory: 3572kb
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: 26ms
memory: 3624kb
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: 25ms
memory: 3572kb
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: 26ms
memory: 3684kb
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: 25ms
memory: 3688kb
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: 26ms
memory: 3540kb
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: 25ms
memory: 3696kb
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: 27ms
memory: 3572kb
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: 0ms
memory: 3480kb
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: 0ms
memory: 3564kb
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: 0ms
memory: 3620kb
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: 0ms
memory: 3636kb
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: 0ms
memory: 3564kb
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: 0ms
memory: 3556kb
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: 0ms
memory: 3476kb
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: 0ms
memory: 3504kb
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: 0ms
memory: 3464kb
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: 0ms
memory: 3476kb
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: 0ms
memory: 3528kb
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: 0ms
memory: 3620kb
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: 0ms
memory: 3676kb
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: 0ms
memory: 3560kb
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: 0ms
memory: 3548kb
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: 0ms
memory: 3600kb
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: 0ms
memory: 3604kb
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: 0ms
memory: 3556kb
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: 0ms
memory: 3564kb
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: 0ms
memory: 3680kb
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: 1ms
memory: 3696kb
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: 4ms
memory: 3752kb
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: 40ms
memory: 4736kb
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: 3632kb
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: 0ms
memory: 3636kb
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: 0ms
memory: 3540kb
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: 33ms
memory: 3568kb
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: 40ms
memory: 4840kb
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: 40ms
memory: 4840kb
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: 33ms
memory: 4768kb
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.