QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#321911#8215. Isomorphic DelightyyyyxhWA 41ms79460kbC++233.6kb2024-02-05 21:34:512024-02-05 21:34:51

Judging History

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

  • [2024-02-05 21:34:51]
  • 评测
  • 测评结果:WA
  • 用时:41ms
  • 内存:79460kb
  • [2024-02-05 21:34:51]
  • 提交

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(){
	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;
	int cc=0,ccc=0,tt=0;
	for(int i=1;i<=num;++i){
		if(adj[i].size()+(i!=1)==3lu) ++cc;
		if(adj[i].size()+(i!=1)==1lu) ++ccc,tt=i+sum;
	}
	if(tt==8) tt=5;
	if(cc==1&&ccc==3) las=tt;
	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;
}

詳細信息

Test #1:

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

input:

1

output:

YES
0

result:

ok Everything ok

Test #2:

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

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: 4ms
memory: 5664kb

input:

4

output:

NO

result:

ok Everything ok

Test #4:

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

input:

2

output:

NO

result:

ok Everything ok

Test #5:

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

input:

3

output:

NO

result:

ok Everything ok

Test #6:

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

input:

5

output:

NO

result:

ok Everything ok

Test #7:

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

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: 20ms
memory: 79148kb

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

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: 23ms
memory: 79192kb

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: 27ms
memory: 79188kb

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: 36ms
memory: 79428kb

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: 15ms
memory: 79460kb

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: 24ms
memory: 79184kb

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

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: 24ms
memory: 79208kb

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: 30ms
memory: 79180kb

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: 29ms
memory: 79192kb

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: 20ms
memory: 79188kb

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: 32ms
memory: 79212kb

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: 41ms
memory: 79156kb

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: 31ms
memory: 79208kb

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: 29ms
memory: 79264kb

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: 19ms
memory: 79152kb

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: 25ms
memory: 79208kb

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: 28ms
memory: 79192kb

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: -100
Wrong Answer
time: 23ms
memory: 79340kb

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:

wrong answer Not asymmetric