QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#321902#8215. Isomorphic DelightyyyyxhWA 33ms87816kbC++233.4kb2024-02-05 21:26:452024-02-05 21:26:46

Judging History

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

  • [2024-02-05 21:26:46]
  • 评测
  • 测评结果:WA
  • 用时:33ms
  • 内存:87816kb
  • [2024-02-05 21:26:45]
  • 提交

answer

#include <cstdio>
#include <vector>
#include <random>
#include <numeric>
#include <algorithm>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
typedef unsigned long long ull;
const int N=2000003;
const int S=53;
__gnu_pbds::gp_hash_table<ull,bool> del;
mt19937 rng(random_device{}());
int n,sum;
int su[N],sv[N],tp;
void add(int u,int v){++tp;su[tp]=u;sv[tp]=v;}
vector<int> sn[N];
int sz[N],cnt;
bool f[N][S],vis[N][S];
int g[N][S];
vector<int> cur;
int len;
struct TreeHash{
	ull p[4][65536];
	TreeHash(){for(int t=0;t<4;++t) iota(p[t],p[t]+65536,0),shuffle(p[t],p[t]+65536,rng);}
	ull Hs(ull x){
		ull res=0;
		res=res<<16|p[0][x>>(0*16)&65535];
		res=res<<16|p[1][x>>(1*16)&65535];
		res=res<<16|p[2][x>>(2*16)&65535];
		res=res<<16|p[3][x>>(3*16)&65535];
		return res;
	};
	ull operator()(ull x){x=Hs(x^(x<<13)^(x>>17));return Hs((x<<3)^(x>>5)^(x<<7));}
}H;
bool dfs(int x,int s){
	if(vis[x][s]&&!f[x][s]) return 0;
	if(vis[x][s]&&g[x][s]<x) return dfs(g[x][s],s);
	vis[x][s]=1;
	if(!x){
		if(!s){
			sn[++cnt]=cur;
			sz[cnt]=len;
			return f[x][s]=1;
		}
		else return f[x][s]=0;
	}
	if(dfs(x-1,s)) f[x][s]=1;
	if(s>=sz[x]){
		cur.emplace_back(x);
		if(dfs(x-1,s-sz[x])) f[x][s]=1,g[x][s]=x;
		else g[x][s]=g[x-1][s];
		cur.pop_back();
	}
	else g[x][s]=g[x-1][s];
	return f[x][s];
}
int num;
vector<int> adj[S];
int build(int p){
	int t=++num;
	for(int x:sn[p]) adj[t].emplace_back(build(x));
	return t;
}
void trav(int p){
	for(int x:adj[p]){
		trav(x);
		printf("%d -> %d\n",p,x);
	}
}
void output(){
	int las=5;
	while(sum<n) add(las,++sum),las=sum;
	printf("%d\n",tp);
	for(int i=1;i<=tp;++i) printf("%d %d\n",su[i],sv[i]);
	exit(0);
}
ull dp[S];
void calc(int p){
	dp[p]=0;
	for(int x:adj[p]){
		calc(x);
		dp[p]+=H(dp[x]);
	}
}
void recalc(int p){
	for(int x:adj[p]){
		dp[x]+=H(dp[p]-H(dp[x]));
		recalc(x);
	}
}
bool check(){
	calc(1);recalc(1);
	sort(dp+1,dp+num+1);
	for(int i=1;i<num;++i) if(dp[i]==dp[i+1]) return 0;
	ull cur=accumulate(dp+1,dp+num+1,0llu);
	if(del[cur]) return 0;
	del[cur]=1;
	return 1;
}
void solve(){
	num=1;
	for(int x:cur) adj[1].emplace_back(build(x));
	if(check()){
		for(int i=1;i<=num;++i)
			for(int j:adj[i]) add(sum+i,sum+j);
		sum+=num;
		if(sum==n) output();
	}
	for(int i=1;i<=num;++i) adj[i].clear();
}
bool go(int x,int s){
	if(vis[x][s]&&!f[x][s]) return 0;
	if(vis[x][s]&&g[x][s]<x) return go(g[x][s],s);
	if(sum+len>n) output();
	vis[x][s]=1;
	if(!x){
		if(!s){
			solve();
			return f[x][s]=1;
		}
		else return f[x][s]=0;
	}
	if(go(x-1,s)) f[x][s]=1;
	if(s>=sz[x]){
		cur.emplace_back(x);
		if(go(x-1,s-sz[x])) f[x][s]=1,g[x][s]=x;
		else g[x][s]=g[x-1][s];
		cur.pop_back();
	}
	else g[x][s]=g[x-1][s];
	return f[x][s];
}
int main(){
	scanf("%d",&n);
	if(n==1){
		puts("YES");
		puts("0");
		return 0;
	}
	if(n<=5){
		puts("NO");
		return 0;
	}
	if(n==6){
		puts("YES");
		puts("6");
		puts("1 2");
		puts("2 3");
		puts("1 3");
		puts("3 4");
		puts("2 5");
		puts("5 6");
		return 0;
	}
	if(n==7){
		puts("YES");
		printf("%d\n",n-1);
		for(int i=2;i<n;++i) printf("%d %d\n",i-1,i);
		printf("3 %d\n",n);
		return 0;
	}
	puts("YES");
	sz[cnt=1]=1;
	for(int i=1;i<=18;++i){
		len=i+1;
		dfs(cnt,i);
	}
	for(int i=1,t=1;;++i){
		len=i;
		while(t<=cnt&&sz[t]*2<=i) ++t;
		go(t-1,i-1);
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 9112kb

input:

1

output:

YES
0

result:

ok Everything ok

Test #2:

score: 0
Accepted
time: 4ms
memory: 7776kb

input:

6

output:

YES
6
1 2
2 3
1 3
3 4
2 5
5 6

result:

ok Everything ok

Test #3:

score: 0
Accepted
time: 3ms
memory: 7040kb

input:

4

output:

NO

result:

ok Everything ok

Test #4:

score: 0
Accepted
time: 3ms
memory: 6436kb

input:

2

output:

NO

result:

ok Everything ok

Test #5:

score: 0
Accepted
time: 3ms
memory: 6484kb

input:

3

output:

NO

result:

ok Everything ok

Test #6:

score: 0
Accepted
time: 3ms
memory: 7584kb

input:

5

output:

NO

result:

ok Everything ok

Test #7:

score: 0
Accepted
time: 3ms
memory: 6760kb

input:

7

output:

YES
6
1 2
2 3
3 4
4 5
5 6
3 7

result:

ok Everything ok

Test #8:

score: 0
Accepted
time: 19ms
memory: 87032kb

input:

8

output:

YES
6
2 3
2 6
2 8
3 4
4 5
6 7

result:

ok Everything ok

Test #9:

score: 0
Accepted
time: 25ms
memory: 86636kb

input:

9

output:

YES
7
2 3
2 6
2 8
3 4
4 5
6 7
5 9

result:

ok Everything ok

Test #10:

score: 0
Accepted
time: 28ms
memory: 84232kb

input:

10

output:

YES
8
2 3
2 6
2 8
3 4
4 5
6 7
5 9
9 10

result:

ok Everything ok

Test #11:

score: 0
Accepted
time: 24ms
memory: 87816kb

input:

11

output:

YES
9
2 3
2 6
2 8
3 4
4 5
6 7
5 9
9 10
10 11

result:

ok Everything ok

Test #12:

score: 0
Accepted
time: 12ms
memory: 86920kb

input:

12

output:

YES
10
2 3
2 6
2 8
3 4
4 5
6 7
5 9
9 10
10 11
11 12

result:

ok Everything ok

Test #13:

score: 0
Accepted
time: 19ms
memory: 87372kb

input:

13

output:

YES
11
2 3
2 6
2 8
3 4
4 5
6 7
5 9
9 10
10 11
11 12
12 13

result:

ok Everything ok

Test #14:

score: 0
Accepted
time: 33ms
memory: 86092kb

input:

14

output:

YES
12
2 3
2 6
2 8
3 4
4 5
6 7
5 9
9 10
10 11
11 12
12 13
13 14

result:

ok Everything ok

Test #15:

score: 0
Accepted
time: 20ms
memory: 87264kb

input:

15

output:

YES
13
2 3
2 6
2 8
3 4
4 5
6 7
5 9
9 10
10 11
11 12
12 13
13 14
14 15

result:

ok Everything ok

Test #16:

score: 0
Accepted
time: 23ms
memory: 87524kb

input:

16

output:

YES
13
2 3
2 6
2 8
3 4
4 5
6 7
9 10
9 14
10 11
10 13
11 12
14 15
15 16

result:

ok Everything ok

Test #17:

score: -100
Wrong Answer
time: 8ms
memory: 85872kb

input:

17

output:

YES
14
2 3
2 6
2 8
3 4
4 5
6 7
9 10
9 14
10 11
10 13
11 12
14 15
15 16
5 17

result:

wrong answer Not asymmetric