QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#19711 | #2492. Hash Function | Wu_Ren | TL | 2448ms | 3892kb | C++14 | 1.3kb | 2022-02-08 16:30:33 | 2022-05-06 06:46:55 |
Judging History
answer
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int n;
ll H,f[32],mod,A0[200],C0[200],A1[200],C1[200];
int s[3][32],s0,s1,s2;
bool v[32];
unordered_map<ll,ll>mp;
inline ll g(ll A,ll C){
return (239*A+153*C)%mod;
}
int main(){
scanf("%d%lld",&n,&H),mod=(1ll<<(2*n-1))-1;
for(int i=0;i<n;i++){
f[i]^=1ll<<i,f[i]^=1ll<<((i-1+2*n)%(2*n));
f[2*i+1]^=1ll<<i,f[2*i+1]^=1ll<<((i-1+2*n)%(2*n));
}
for(int i=n;i<2*n;i++){
f[i]^=1ll<<i,f[i]^=1ll<<((i-1+2*n)%(2*n));
f[4*n-2-2*i]^=1ll<<i,f[4*n-2-2*i]^=1ll<<((i-1+2*n)%(2*n));
}
for(int i=1;i<n-1;i+=2) s[0][s0++]=i,v[i]=1;
for(int i=2*n-2;i>n;i-=2) s[1][s1++]=i,v[i]=1;
for(int i=0;i<2*n;i++) if(!v[i]) s[2][s2++]=i;
for(int S=0;S<(1<<s0);S++) for(int i=0;i<s0;i++) if((S>>i)&1) A0[S]^=1ll<<s[0][i],C0[S]^=f[s[0][i]];
for(int S=0;S<(1<<s1);S++) for(int i=0;i<s1;i++) if((S>>i)&1) A1[S]^=1ll<<s[1][i],C1[S]^=f[s[1][i]];
for(int S2=0;S2<(1<<s2);S2++){
ll A=0,C=0;mp.clear();
for(int i=0;i<s2;i++) if((S2>>i)&1) A^=1ll<<s[2][i],C^=f[s[2][i]];
ll gAC=g(A,C);
for(int S=0;S<(1<<s1);S++) mp[(g(A^A1[S],C^C1[S])-gAC+mod)%mod]=A1[S];
for(int S=0;S<(1<<s0);S++){
ll w=(H-g(A^A0[S],C^C0[S])+mod)%mod;
if(mp.count(w)) printf("%lld\n",A^A0[S]^mp[w]),exit(0);
}
}
puts("NTFtxdy");
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 3776kb
input:
4 83
output:
13
result:
ok good solution
Test #2:
score: 0
Accepted
time: 5ms
memory: 3832kb
input:
10 497091
output:
153014
result:
ok good solution
Test #3:
score: 0
Accepted
time: 1ms
memory: 3812kb
input:
4 55
output:
73
result:
ok good solution
Test #4:
score: 0
Accepted
time: 181ms
memory: 3836kb
input:
15 444650548
output:
377677832
result:
ok good solution
Test #5:
score: 0
Accepted
time: 138ms
memory: 3748kb
input:
14 114355996
output:
119238393
result:
ok good solution
Test #6:
score: 0
Accepted
time: 1ms
memory: 3836kb
input:
16 0
output:
0
result:
ok good solution
Test #7:
score: 0
Accepted
time: 3ms
memory: 3684kb
input:
3 22
output:
8
result:
ok good solution
Test #8:
score: 0
Accepted
time: 3ms
memory: 3808kb
input:
8 8319
output:
15407
result:
ok good solution
Test #9:
score: 0
Accepted
time: 46ms
memory: 3692kb
input:
12 7629490
output:
14052612
result:
ok good solution
Test #10:
score: 0
Accepted
time: 2ms
memory: 3740kb
input:
2 2
output:
3
result:
ok good solution
Test #11:
score: 0
Accepted
time: 2ms
memory: 3692kb
input:
16 0
output:
0
result:
ok good solution
Test #12:
score: 0
Accepted
time: 3ms
memory: 3892kb
input:
16 0
output:
0
result:
ok good solution
Test #13:
score: 0
Accepted
time: 0ms
memory: 3692kb
input:
16 0
output:
0
result:
ok good solution
Test #14:
score: 0
Accepted
time: 4ms
memory: 3748kb
input:
11 1086647
output:
1875946
result:
ok good solution
Test #15:
score: 0
Accepted
time: 4ms
memory: 3748kb
input:
11 188671
output:
393405
result:
ok good solution
Test #16:
score: 0
Accepted
time: 2ms
memory: 3888kb
input:
11 2028522
output:
424106
result:
ok good solution
Test #17:
score: 0
Accepted
time: 85ms
memory: 3828kb
input:
13 23601796
output:
40518521
result:
ok good solution
Test #18:
score: 0
Accepted
time: 3ms
memory: 3688kb
input:
8 29405
output:
7325
result:
ok good solution
Test #19:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
7 2218
output:
3174
result:
ok good solution
Test #20:
score: 0
Accepted
time: 3ms
memory: 3884kb
input:
7 432
output:
662
result:
ok good solution
Test #21:
score: 0
Accepted
time: 7ms
memory: 3812kb
input:
11 899191
output:
1626482
result:
ok good solution
Test #22:
score: 0
Accepted
time: 1ms
memory: 3816kb
input:
5 494
output:
281
result:
ok good solution
Test #23:
score: 0
Accepted
time: 2ms
memory: 3780kb
input:
8 13862
output:
12212
result:
ok good solution
Test #24:
score: 0
Accepted
time: 7ms
memory: 3680kb
input:
11 899027
output:
1622100
result:
ok good solution
Test #25:
score: 0
Accepted
time: 3ms
memory: 3812kb
input:
8 7446
output:
49853
result:
ok good solution
Test #26:
score: 0
Accepted
time: 1ms
memory: 3824kb
input:
3 12
output:
6
result:
ok good solution
Test #27:
score: 0
Accepted
time: 1ms
memory: 3812kb
input:
8 6258
output:
18666
result:
ok good solution
Test #28:
score: 0
Accepted
time: 290ms
memory: 3836kb
input:
15 191474555
output:
411455767
result:
ok good solution
Test #29:
score: 0
Accepted
time: 3ms
memory: 3812kb
input:
3 17
output:
20
result:
ok good solution
Test #30:
score: 0
Accepted
time: 219ms
memory: 3800kb
input:
15 161474861
output:
318717104
result:
ok good solution
Test #31:
score: 0
Accepted
time: 3ms
memory: 3744kb
input:
10 180816
output:
81147
result:
ok good solution
Test #32:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
4 116
output:
81
result:
ok good solution
Test #33:
score: 0
Accepted
time: 1022ms
memory: 3840kb
input:
16 1196684556
output:
567748713
result:
ok good solution
Test #34:
score: 0
Accepted
time: 700ms
memory: 3892kb
input:
16 1087033358
output:
458416341
result:
ok good solution
Test #35:
score: 0
Accepted
time: 783ms
memory: 3836kb
input:
16 2112546660
output:
1321210677
result:
ok good solution
Test #36:
score: 0
Accepted
time: 2324ms
memory: 3836kb
input:
16 130507716
output:
3358127644
result:
ok good solution
Test #37:
score: 0
Accepted
time: 1727ms
memory: 3692kb
input:
16 1531459999
output:
1004811660
result:
ok good solution
Test #38:
score: 0
Accepted
time: 196ms
memory: 3800kb
input:
16 1905706077
output:
1437054237
result:
ok good solution
Test #39:
score: 0
Accepted
time: 2448ms
memory: 3692kb
input:
16 1584950777
output:
2565491169
result:
ok good solution
Test #40:
score: 0
Accepted
time: 388ms
memory: 3840kb
input:
16 1112585098
output:
312451907
result:
ok good solution
Test #41:
score: 0
Accepted
time: 668ms
memory: 3800kb
input:
16 1527899944
output:
1488817943
result:
ok good solution
Test #42:
score: -100
Time Limit Exceeded
input:
16 1234237908