QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#19711#2492. Hash FunctionWu_RenTL 2448ms3892kbC++141.3kb2022-02-08 16:30:332022-05-06 06:46:55

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-06 06:46:55]
  • 评测
  • 测评结果:TL
  • 用时:2448ms
  • 内存:3892kb
  • [2022-02-08 16:30:33]
  • 提交

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

output:


result: