QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#321941#8215. Isomorphic DelightyyyyxhTL 1276ms8396kbC++234.0kb2024-02-05 22:30:122024-02-05 22:30:12

Judging History

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

  • [2024-02-05 22:30:12]
  • 评测
  • 测评结果:TL
  • 用时:1276ms
  • 内存:8396kb
  • [2024-02-05 22:30:12]
  • 提交

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+sum;
		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,t=1;;++i){
		if(i&1){
			len=(i>>1)+1;
			dfs(cnt,i>>1);
		}
		len=i;
		while(t<=cnt&&sz[t]*2<=i) ++t;
		go(t-1,i-1);
	}
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 6ms
memory: 7168kb

input:

1

output:

YES
0

result:

ok Everything ok

Test #2:

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

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: 6ms
memory: 7264kb

input:

4

output:

NO

result:

ok Everything ok

Test #4:

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

input:

2

output:

NO

result:

ok Everything ok

Test #5:

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

input:

3

output:

NO

result:

ok Everything ok

Test #6:

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

input:

5

output:

NO

result:

ok Everything ok

Test #7:

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

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: 3ms
memory: 6164kb

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: 5ms
memory: 5904kb

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: 6ms
memory: 6180kb

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: 5ms
memory: 5904kb

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: 3ms
memory: 5904kb

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: 5ms
memory: 6156kb

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: 2ms
memory: 5956kb

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: 6ms
memory: 5960kb

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: 3ms
memory: 5892kb

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: 0
Accepted
time: 0ms
memory: 5900kb

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
16 17

result:

ok Everything ok

Test #18:

score: 0
Accepted
time: 0ms
memory: 5892kb

input:

18

output:

YES
15
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
16 17
17 18

result:

ok Everything ok

Test #19:

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

input:

19

output:

YES
16
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
16 17
17 18
18 19

result:

ok Everything ok

Test #20:

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

input:

598

output:

YES
544
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
17 18
17 22
17 25
18 19
18 21
19 20
22 23
23 24
26 27
26 31
26 34
27 28
28 29
29 30
31 32
32 33
35 36
35 40
36 37
37 38
38 39
40 41
40 43
41 42
44 45
44 49
44 52
45 46
45 48
46 47
49 50
50 51
52 53
54 55
54 59
54 62
55 56
56 57
...

result:

ok Everything ok

Test #21:

score: 0
Accepted
time: 6ms
memory: 5916kb

input:

245

output:

YES
221
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
17 18
17 22
17 25
18 19
18 21
19 20
22 23
23 24
26 27
26 31
26 34
27 28
28 29
29 30
31 32
32 33
35 36
35 40
36 37
37 38
38 39
40 41
40 43
41 42
44 45
44 49
44 52
45 46
45 48
46 47
49 50
50 51
52 53
54 55
54 59
54 62
55 56
56 57
...

result:

ok Everything ok

Test #22:

score: 0
Accepted
time: 8ms
memory: 5940kb

input:

793

output:

YES
724
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
17 18
17 22
17 25
18 19
18 21
19 20
22 23
23 24
26 27
26 31
26 34
27 28
28 29
29 30
31 32
32 33
35 36
35 40
36 37
37 38
38 39
40 41
40 43
41 42
44 45
44 49
44 52
45 46
45 48
46 47
49 50
50 51
52 53
54 55
54 59
54 62
55 56
56 57
...

result:

ok Everything ok

Test #23:

score: 0
Accepted
time: 6ms
memory: 6872kb

input:

133

output:

YES
119
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
17 18
17 22
17 25
18 19
18 21
19 20
22 23
23 24
26 27
26 31
26 34
27 28
28 29
29 30
31 32
32 33
35 36
35 40
36 37
37 38
38 39
40 41
40 43
41 42
44 45
44 49
44 52
45 46
45 48
46 47
49 50
50 51
52 53
54 55
54 59
54 62
55 56
56 57
...

result:

ok Everything ok

Test #24:

score: 0
Accepted
time: 8ms
memory: 7100kb

input:

681

output:

YES
620
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
17 18
17 22
17 25
18 19
18 21
19 20
22 23
23 24
26 27
26 31
26 34
27 28
28 29
29 30
31 32
32 33
35 36
35 40
36 37
37 38
38 39
40 41
40 43
41 42
44 45
44 49
44 52
45 46
45 48
46 47
49 50
50 51
52 53
54 55
54 59
54 62
55 56
56 57
...

result:

ok Everything ok

Test #25:

score: 0
Accepted
time: 9ms
memory: 8004kb

input:

922

output:

YES
843
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
17 18
17 22
17 25
18 19
18 21
19 20
22 23
23 24
26 27
26 31
26 34
27 28
28 29
29 30
31 32
32 33
35 36
35 40
36 37
37 38
38 39
40 41
40 43
41 42
44 45
44 49
44 52
45 46
45 48
46 47
49 50
50 51
52 53
54 55
54 59
54 62
55 56
56 57
...

result:

ok Everything ok

Test #26:

score: 0
Accepted
time: 8ms
memory: 7076kb

input:

876

output:

YES
800
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
17 18
17 22
17 25
18 19
18 21
19 20
22 23
23 24
26 27
26 31
26 34
27 28
28 29
29 30
31 32
32 33
35 36
35 40
36 37
37 38
38 39
40 41
40 43
41 42
44 45
44 49
44 52
45 46
45 48
46 47
49 50
50 51
52 53
54 55
54 59
54 62
55 56
56 57
...

result:

ok Everything ok

Test #27:

score: 0
Accepted
time: 46ms
memory: 8396kb

input:

7740

output:

YES
7191
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
17 18
17 22
17 25
18 19
18 21
19 20
22 23
23 24
26 27
26 31
26 34
27 28
28 29
29 30
31 32
32 33
35 36
35 40
36 37
37 38
38 39
40 41
40 43
41 42
44 45
44 49
44 52
45 46
45 48
46 47
49 50
50 51
52 53
54 55
54 59
54 62
55 56
56 57...

result:

ok Everything ok

Test #28:

score: 0
Accepted
time: 10ms
memory: 7160kb

input:

2460

output:

YES
2268
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
17 18
17 22
17 25
18 19
18 21
19 20
22 23
23 24
26 27
26 31
26 34
27 28
28 29
29 30
31 32
32 33
35 36
35 40
36 37
37 38
38 39
40 41
40 43
41 42
44 45
44 49
44 52
45 46
45 48
46 47
49 50
50 51
52 53
54 55
54 59
54 62
55 56
56 57...

result:

ok Everything ok

Test #29:

score: 0
Accepted
time: 45ms
memory: 6136kb

input:

7533

output:

YES
6998
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
17 18
17 22
17 25
18 19
18 21
19 20
22 23
23 24
26 27
26 31
26 34
27 28
28 29
29 30
31 32
32 33
35 36
35 40
36 37
37 38
38 39
40 41
40 43
41 42
44 45
44 49
44 52
45 46
45 48
46 47
49 50
50 51
52 53
54 55
54 59
54 62
55 56
56 57...

result:

ok Everything ok

Test #30:

score: 0
Accepted
time: 39ms
memory: 6020kb

input:

5957

output:

YES
5527
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
17 18
17 22
17 25
18 19
18 21
19 20
22 23
23 24
26 27
26 31
26 34
27 28
28 29
29 30
31 32
32 33
35 36
35 40
36 37
37 38
38 39
40 41
40 43
41 42
44 45
44 49
44 52
45 46
45 48
46 47
49 50
50 51
52 53
54 55
54 59
54 62
55 56
56 57...

result:

ok Everything ok

Test #31:

score: 0
Accepted
time: 1170ms
memory: 7344kb

input:

92651

output:

YES
87225
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
17 18
17 22
17 25
18 19
18 21
19 20
22 23
23 24
26 27
26 31
26 34
27 28
28 29
29 30
31 32
32 33
35 36
35 40
36 37
37 38
38 39
40 41
40 43
41 42
44 45
44 49
44 52
45 46
45 48
46 47
49 50
50 51
52 53
54 55
54 59
54 62
55 56
56 5...

result:

ok Everything ok

Test #32:

score: 0
Accepted
time: 629ms
memory: 6856kb

input:

58779

output:

YES
55235
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
17 18
17 22
17 25
18 19
18 21
19 20
22 23
23 24
26 27
26 31
26 34
27 28
28 29
29 30
31 32
32 33
35 36
35 40
36 37
37 38
38 39
40 41
40 43
41 42
44 45
44 49
44 52
45 46
45 48
46 47
49 50
50 51
52 53
54 55
54 59
54 62
55 56
56 5...

result:

ok Everything ok

Test #33:

score: 0
Accepted
time: 83ms
memory: 6216kb

input:

12203

output:

YES
11374
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
17 18
17 22
17 25
18 19
18 21
19 20
22 23
23 24
26 27
26 31
26 34
27 28
28 29
29 30
31 32
32 33
35 36
35 40
36 37
37 38
38 39
40 41
40 43
41 42
44 45
44 49
44 52
45 46
45 48
46 47
49 50
50 51
52 53
54 55
54 59
54 62
55 56
56 5...

result:

ok Everything ok

Test #34:

score: 0
Accepted
time: 583ms
memory: 6836kb

input:

55627

output:

YES
52258
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
17 18
17 22
17 25
18 19
18 21
19 20
22 23
23 24
26 27
26 31
26 34
27 28
28 29
29 30
31 32
32 33
35 36
35 40
36 37
37 38
38 39
40 41
40 43
41 42
44 45
44 49
44 52
45 46
45 48
46 47
49 50
50 51
52 53
54 55
54 59
54 62
55 56
56 5...

result:

ok Everything ok

Test #35:

score: 0
Accepted
time: 1276ms
memory: 7372kb

input:

99051

output:

YES
93269
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
17 18
17 22
17 25
18 19
18 21
19 20
22 23
23 24
26 27
26 31
26 34
27 28
28 29
29 30
31 32
32 33
35 36
35 40
36 37
37 38
38 39
40 41
40 43
41 42
44 45
44 49
44 52
45 46
45 48
46 47
49 50
50 51
52 53
54 55
54 59
54 62
55 56
56 5...

result:

ok Everything ok

Test #36:

score: -100
Time Limit Exceeded

input:

811713

output:


result: