QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#321938#8215. Isomorphic DelightyyyyxhWA 27ms81488kbC++234.0kb2024-02-05 22:22:302024-02-05 22:22:31

Judging History

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

  • [2024-02-05 22:22:31]
  • 评测
  • 测评结果:WA
  • 用时:27ms
  • 内存:81488kb
  • [2024-02-05 22:22:30]
  • 提交

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,las;
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(){
	// printf("%d\n",n-sum);
	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];
int ff[S],diam;
void calc(int p){
	dp[p]=0;ff[p]=0;
	for(int x:adj[p]){
		calc(x);
		diam=max(ff[p]+ff[x]+1,diam);
		ff[p]=max(ff[p],ff[x]+1);
		dp[p]+=H(dp[x]);
	}
}
void recalc(int p){
	for(int x:adj[p]){
		dp[x]+=H(dp[p]-H(dp[x]));
		recalc(x);
	}
}
vector<int> ss[N];
int mx,tt;
void find(int p,int ft,int d){
	if(d>mx) mx=d,tt=p;
	for(int x:ss[p]){
		if(x==ft) continue;
		find(x,p,d+1);
	}
}
bool check(){
	diam=0;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;
	int cc=0,ccc=0,rt=0;
	for(int i=1;i<=num;++i){
		if(adj[i].size()+(i!=1)==3lu){rt=i;++cc;}
		if(adj[i].size()+(i!=1)==1lu) ++ccc;
	}
	if(cc==1&&ccc==3&&diam==num-2){
		for(int i=1;i<=num;++i)
			for(int j:adj[i]){
				ss[i].emplace_back(j);
				ss[j].emplace_back(i);
			}
		mx=0;
		find(rt,0,0);
		las=tt;
		for(int i=1;i<=num;++i) ss[i].clear();
	}
	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: 2ms
memory: 6348kb

input:

1

output:

YES
0

result:

ok Everything ok

Test #2:

score: 0
Accepted
time: 5ms
memory: 7024kb

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: 0ms
memory: 7888kb

input:

4

output:

NO

result:

ok Everything ok

Test #4:

score: 0
Accepted
time: 5ms
memory: 6560kb

input:

2

output:

NO

result:

ok Everything ok

Test #5:

score: 0
Accepted
time: 5ms
memory: 7444kb

input:

3

output:

NO

result:

ok Everything ok

Test #6:

score: 0
Accepted
time: 5ms
memory: 6820kb

input:

5

output:

NO

result:

ok Everything ok

Test #7:

score: 0
Accepted
time: 2ms
memory: 7272kb

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: 81488kb

input:

8

output:

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

result:

ok Everything ok

Test #9:

score: -100
Wrong Answer
time: 27ms
memory: 81120kb

input:

9

output:

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

result:

wrong answer Not asymmetric