QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#334945#8215. Isomorphic Delightucup-team1209#AC ✓875ms142192kbC++203.2kb2024-02-22 15:25:072024-02-22 15:25:07

Judging History

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

  • [2024-02-22 15:25:07]
  • 评测
  • 测评结果:AC
  • 用时:875ms
  • 内存:142192kb
  • [2024-02-22 15:25:07]
  • 提交

answer

#include<bits/stdc++.h>
using std::cin;
using std::cout;
using pr = std::pair<int, int>;
using u64 = unsigned long long;
const u64 C = 12894718241;
u64 f(u64 x) {
	x ^= x << 13;
	x ^= x >> 7;
	x ^= x << 17;
	return x;
}
std::vector<pr> edge;

const int N = 3000005;
std::vector<int> son[N];

void cyctree(int n, int base = 0) {
	for(int i = 2;i <= n - 3;++i) {
		edge.emplace_back(base + i, base + i - 1);
	}
	edge.emplace_back(base + 1, base + n - 3);
	edge.emplace_back(base + 1, base + n - 2);
	edge.emplace_back(base + 2, base + n - 1);
	edge.emplace_back(base + n - 1, base + n);
}
int tct;
int tree(int x) {
	int p = ++tct;
	for(int z : son[x]) {
		edge.emplace_back(p, tree(z));
	}
	return p;
}


u64 hash[N];
int size[N];
int ed[N];
int cc;
int n;

int okcc = 0;
std::map<std::vector<u64>, int> map;

void hashset(int x) {
	if(son[x].size() > 1) return ;
	std::vector<u64> hashs;
	auto dfs = [&](int x, u64 ancv, auto dfs) -> void {
		hashs.push_back(hash[x] + ancv);
		for(int i : son[x]) {
			dfs(i, f(hash[x] + ancv - f(hash[i])), dfs);
		}
	};
	dfs(x, 0, dfs);
	sort(hashs.begin(), hashs.end());
	for(int i = 1;i < (int) hashs.size();++i) {
		if(hashs[i] == hashs[i - 1]) {
			return ;
		}
	}
	okcc += hashs.size();
	map[hashs] = x;
}



int main() {
	std::ios::sync_with_stdio(false), cin.tie(0);
	size[1] = 1, hash[1] = C, ed[1] = 1, cc = 1;
	hashset(1);
	const int M = 21;

	for(int i = 2;i <= M;++i) {
		std::vector<int> s;
		auto dfs = [&](int rem, int idx, auto & s, auto dfs) {
			if(rem == 0) {
				size[++cc] = i;
				hash[cc] += C;
				son[cc] = s;
				for(int x : s) {
					hash[cc] += f(hash[x]);
				}
				hashset(cc);
				return ;
			}
			idx = std::min(idx, ed[rem]);
			for(int i = idx;i >= 1;--i) {
				s.push_back(i);
				dfs(rem - size[i], i - 1, s, dfs);
				s.pop_back();
			}
		};
		dfs(i - 1, 1e9, s, dfs);
		ed[i] = cc;
	}
	std::vector<std::pair<int, int>> vecs;
	for(auto & [a, b] : map) {
		vecs.emplace_back(size[b], b);
	}

	sort(vecs.begin(), vecs.end());
	auto greedy = [&](int n, std::vector<int> v) {
		if(v.empty() && n <= 6) return v;
		for(int i = 1;n;++i) {
			if(vecs[i].first <= n) {
				v.push_back(vecs[i].second);
				n -= vecs[i].first;
			} else {
				if(size[v[0]] < vecs[i].first) {
					for(int j = 0;j < (int) v.size();++j) {
						const int sub = vecs[i].first - size[v[j]];
						if(sub <= n) {
							n -= sub;
							v.erase(v.begin() + j);
							v.push_back(vecs[i].second);
							break;
						}
					}
				}
			}
		}
		return v;
	};
	std::vector<int> ans;
	for(int idx = 0;idx < 2;++idx) {
		std::vector<int> v;
	}
	cin >> n;
	auto A = greedy(n, {});
	if(n >= 7 || n == 1) {
		auto B = greedy(n - 1, {1});
		if(B.size() > A.size()) {
			A = B;
		}
	}
	int cyc_size = n;
	for(int x : A) cyc_size -= size[x];
	if(cyc_size >= 6 || cyc_size == 0) {
		cout << "YES" << '\n';
		if(cyc_size) cyctree(tct = cyc_size);
		for(auto x : A) {
			tree(x);
		}
		cout << edge.size() << '\n';
		for(auto [a, b] : edge) {
			cout << a << ' ' << b << '\n';
		}
	} else {
		cout << "NO" << '\n';
	}
//	cin >> n;

}

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

*/

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 781ms
memory: 133392kb

input:

1

output:

YES
0

result:

ok Everything ok

Test #2:

score: 0
Accepted
time: 793ms
memory: 133524kb

input:

6

output:

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

result:

ok Everything ok

Test #3:

score: 0
Accepted
time: 810ms
memory: 133640kb

input:

4

output:

NO

result:

ok Everything ok

Test #4:

score: 0
Accepted
time: 773ms
memory: 133300kb

input:

2

output:

NO

result:

ok Everything ok

Test #5:

score: 0
Accepted
time: 793ms
memory: 133340kb

input:

3

output:

NO

result:

ok Everything ok

Test #6:

score: 0
Accepted
time: 798ms
memory: 133304kb

input:

5

output:

NO

result:

ok Everything ok

Test #7:

score: 0
Accepted
time: 796ms
memory: 133484kb

input:

7

output:

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

result:

ok Everything ok

Test #8:

score: 0
Accepted
time: 793ms
memory: 133476kb

input:

8

output:

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

result:

ok Everything ok

Test #9:

score: 0
Accepted
time: 771ms
memory: 133472kb

input:

9

output:

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

result:

ok Everything ok

Test #10:

score: 0
Accepted
time: 774ms
memory: 133480kb

input:

10

output:

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

result:

ok Everything ok

Test #11:

score: 0
Accepted
time: 774ms
memory: 133416kb

input:

11

output:

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

result:

ok Everything ok

Test #12:

score: 0
Accepted
time: 756ms
memory: 133596kb

input:

12

output:

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

result:

ok Everything ok

Test #13:

score: 0
Accepted
time: 774ms
memory: 133644kb

input:

13

output:

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

result:

ok Everything ok

Test #14:

score: 0
Accepted
time: 772ms
memory: 133400kb

input:

14

output:

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

result:

ok Everything ok

Test #15:

score: 0
Accepted
time: 737ms
memory: 133628kb

input:

15

output:

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

result:

ok Everything ok

Test #16:

score: 0
Accepted
time: 749ms
memory: 133596kb

input:

16

output:

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

result:

ok Everything ok

Test #17:

score: 0
Accepted
time: 771ms
memory: 133520kb

input:

17

output:

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

result:

ok Everything ok

Test #18:

score: 0
Accepted
time: 781ms
memory: 133500kb

input:

18

output:

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

result:

ok Everything ok

Test #19:

score: 0
Accepted
time: 762ms
memory: 133480kb

input:

19

output:

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

result:

ok Everything ok

Test #20:

score: 0
Accepted
time: 797ms
memory: 133480kb

input:

598

output:

YES
544
7 8
6 7
5 6
4 5
4 9
3 4
2 3
16 17
15 16
14 15
14 18
13 14
12 13
11 12
10 11
24 25
23 24
22 23
22 26
21 22
21 27
20 21
19 20
34 35
33 34
32 33
31 32
30 31
30 36
29 30
28 29
44 45
43 44
42 43
42 46
41 42
40 41
39 40
38 39
37 38
53 54
52 53
51 52
50 51
50 55
49 50
49 56
48 49
47 48
64 65
63 64
...

result:

ok Everything ok

Test #21:

score: 0
Accepted
time: 816ms
memory: 133396kb

input:

245

output:

YES
221
5 6
4 5
3 4
3 7
2 3
1 2
13 14
12 13
11 12
10 11
10 15
9 10
8 9
22 23
21 22
20 21
20 24
19 20
18 19
17 18
16 17
30 31
29 30
28 29
28 32
27 28
27 33
26 27
25 26
40 41
39 40
38 39
37 38
36 37
36 42
35 36
34 35
50 51
49 50
48 49
48 52
47 48
46 47
45 46
44 45
43 44
59 60
58 59
57 58
56 57
56 61
5...

result:

ok Everything ok

Test #22:

score: 0
Accepted
time: 806ms
memory: 133500kb

input:

793

output:

YES
724
7 8
6 7
5 6
4 5
4 9
3 4
2 3
16 17
15 16
14 15
14 18
13 14
12 13
11 12
10 11
24 25
23 24
22 23
22 26
21 22
21 27
20 21
19 20
34 35
33 34
32 33
31 32
30 31
30 36
29 30
28 29
44 45
43 44
42 43
42 46
41 42
40 41
39 40
38 39
37 38
53 54
52 53
51 52
50 51
50 55
49 50
49 56
48 49
47 48
64 65
63 64
...

result:

ok Everything ok

Test #23:

score: 0
Accepted
time: 760ms
memory: 133612kb

input:

133

output:

YES
119
8 9
7 8
6 7
6 10
5 6
4 5
3 4
2 3
16 17
15 16
14 15
14 18
13 14
13 19
12 13
11 12
26 27
25 26
24 25
23 24
22 23
22 28
21 22
20 21
35 36
34 35
33 34
32 33
32 37
31 32
31 38
30 31
29 30
46 47
45 46
44 45
43 44
42 43
41 42
41 48
40 41
39 40
55 56
54 55
53 54
53 57
52 53
51 52
51 58
50 51
49 50
6...

result:

ok Everything ok

Test #24:

score: 0
Accepted
time: 771ms
memory: 133644kb

input:

681

output:

YES
620
6 7
5 6
4 5
4 8
3 4
2 3
14 15
13 14
12 13
11 12
11 16
10 11
9 10
23 24
22 23
21 22
21 25
20 21
19 20
18 19
17 18
31 32
30 31
29 30
29 33
28 29
28 34
27 28
26 27
41 42
40 41
39 40
38 39
37 38
37 43
36 37
35 36
51 52
50 51
49 50
49 53
48 49
47 48
46 47
45 46
44 45
60 61
59 60
58 59
57 58
57 62...

result:

ok Everything ok

Test #25:

score: 0
Accepted
time: 762ms
memory: 133492kb

input:

922

output:

YES
843
7 8
6 7
5 6
4 5
4 9
3 4
2 3
16 17
15 16
14 15
14 18
13 14
12 13
11 12
10 11
24 25
23 24
22 23
22 26
21 22
21 27
20 21
19 20
34 35
33 34
32 33
31 32
30 31
30 36
29 30
28 29
44 45
43 44
42 43
42 46
41 42
40 41
39 40
38 39
37 38
53 54
52 53
51 52
50 51
50 55
49 50
49 56
48 49
47 48
64 65
63 64
...

result:

ok Everything ok

Test #26:

score: 0
Accepted
time: 808ms
memory: 133564kb

input:

876

output:

YES
800
6 7
5 6
4 5
4 8
3 4
2 3
14 15
13 14
12 13
11 12
11 16
10 11
9 10
23 24
22 23
21 22
21 25
20 21
19 20
18 19
17 18
31 32
30 31
29 30
29 33
28 29
28 34
27 28
26 27
41 42
40 41
39 40
38 39
37 38
37 43
36 37
35 36
51 52
50 51
49 50
49 53
48 49
47 48
46 47
45 46
44 45
60 61
59 60
58 59
57 58
57 62...

result:

ok Everything ok

Test #27:

score: 0
Accepted
time: 802ms
memory: 133648kb

input:

7740

output:

YES
7191
6 7
5 6
4 5
4 8
3 4
2 3
14 15
13 14
12 13
11 12
11 16
10 11
9 10
23 24
22 23
21 22
21 25
20 21
19 20
18 19
17 18
31 32
30 31
29 30
29 33
28 29
28 34
27 28
26 27
41 42
40 41
39 40
38 39
37 38
37 43
36 37
35 36
51 52
50 51
49 50
49 53
48 49
47 48
46 47
45 46
44 45
60 61
59 60
58 59
57 58
57 6...

result:

ok Everything ok

Test #28:

score: 0
Accepted
time: 860ms
memory: 133520kb

input:

2460

output:

YES
2268
7 8
6 7
5 6
4 5
4 9
3 4
2 3
16 17
15 16
14 15
14 18
13 14
12 13
11 12
10 11
24 25
23 24
22 23
22 26
21 22
21 27
20 21
19 20
34 35
33 34
32 33
31 32
30 31
30 36
29 30
28 29
44 45
43 44
42 43
42 46
41 42
40 41
39 40
38 39
37 38
53 54
52 53
51 52
50 51
50 55
49 50
49 56
48 49
47 48
64 65
63 64...

result:

ok Everything ok

Test #29:

score: 0
Accepted
time: 875ms
memory: 133480kb

input:

7533

output:

YES
6998
6 7
5 6
4 5
4 8
3 4
2 3
14 15
13 14
12 13
11 12
11 16
10 11
9 10
23 24
22 23
21 22
21 25
20 21
19 20
18 19
17 18
31 32
30 31
29 30
29 33
28 29
28 34
27 28
26 27
41 42
40 41
39 40
38 39
37 38
37 43
36 37
35 36
50 51
49 50
48 49
47 48
47 52
46 47
46 53
45 46
44 45
61 62
60 61
59 60
58 59
57 5...

result:

ok Everything ok

Test #30:

score: 0
Accepted
time: 873ms
memory: 133644kb

input:

5957

output:

YES
5527
6 7
5 6
4 5
4 8
3 4
2 3
14 15
13 14
12 13
11 12
11 16
10 11
9 10
23 24
22 23
21 22
21 25
20 21
19 20
18 19
17 18
31 32
30 31
29 30
29 33
28 29
28 34
27 28
26 27
41 42
40 41
39 40
38 39
37 38
37 43
36 37
35 36
51 52
50 51
49 50
49 53
48 49
47 48
46 47
45 46
44 45
60 61
59 60
58 59
57 58
57 6...

result:

ok Everything ok

Test #31:

score: 0
Accepted
time: 825ms
memory: 134400kb

input:

92651

output:

YES
87225
6 7
5 6
4 5
4 8
3 4
2 3
15 16
14 15
13 14
13 17
12 13
11 12
10 11
9 10
23 24
22 23
21 22
21 25
20 21
20 26
19 20
18 19
33 34
32 33
31 32
30 31
29 30
29 35
28 29
27 28
43 44
42 43
41 42
41 45
40 41
39 40
38 39
37 38
36 37
52 53
51 52
50 51
49 50
49 54
48 49
48 55
47 48
46 47
63 64
62 63
61 ...

result:

ok Everything ok

Test #32:

score: 0
Accepted
time: 844ms
memory: 134124kb

input:

58779

output:

YES
55235
7 8
6 7
5 6
4 5
4 9
3 4
2 3
16 17
15 16
14 15
14 18
13 14
12 13
11 12
10 11
24 25
23 24
22 23
22 26
21 22
21 27
20 21
19 20
34 35
33 34
32 33
31 32
30 31
30 36
29 30
28 29
44 45
43 44
42 43
42 46
41 42
40 41
39 40
38 39
37 38
53 54
52 53
51 52
50 51
50 55
49 50
49 56
48 49
47 48
64 65
63 6...

result:

ok Everything ok

Test #33:

score: 0
Accepted
time: 848ms
memory: 133404kb

input:

12203

output:

YES
11374
6 7
5 6
4 5
4 8
3 4
2 3
15 16
14 15
13 14
13 17
12 13
11 12
10 11
9 10
23 24
22 23
21 22
21 25
20 21
20 26
19 20
18 19
33 34
32 33
31 32
30 31
29 30
29 35
28 29
27 28
43 44
42 43
41 42
41 45
40 41
39 40
38 39
37 38
36 37
52 53
51 52
50 51
49 50
49 54
48 49
48 55
47 48
46 47
63 64
62 63
61 ...

result:

ok Everything ok

Test #34:

score: 0
Accepted
time: 834ms
memory: 134056kb

input:

55627

output:

YES
52258
7 8
6 7
5 6
4 5
4 9
3 4
2 3
16 17
15 16
14 15
14 18
13 14
12 13
11 12
10 11
24 25
23 24
22 23
22 26
21 22
21 27
20 21
19 20
34 35
33 34
32 33
31 32
30 31
30 36
29 30
28 29
44 45
43 44
42 43
42 46
41 42
40 41
39 40
38 39
37 38
53 54
52 53
51 52
50 51
50 55
49 50
49 56
48 49
47 48
64 65
63 6...

result:

ok Everything ok

Test #35:

score: 0
Accepted
time: 854ms
memory: 134332kb

input:

99051

output:

YES
93269
6 7
5 6
4 5
4 8
3 4
2 3
14 15
13 14
12 13
11 12
11 16
10 11
9 10
23 24
22 23
21 22
21 25
20 21
19 20
18 19
17 18
31 32
30 31
29 30
29 33
28 29
28 34
27 28
26 27
41 42
40 41
39 40
38 39
37 38
37 43
36 37
35 36
51 52
50 51
49 50
49 53
48 49
47 48
46 47
45 46
44 45
60 61
59 60
58 59
57 58
57 ...

result:

ok Everything ok

Test #36:

score: 0
Accepted
time: 855ms
memory: 142192kb

input:

811713

output:

YES
770513
7 8
6 7
5 6
4 5
4 9
3 4
2 3
16 17
15 16
14 15
14 18
13 14
12 13
11 12
10 11
24 25
23 24
22 23
22 26
21 22
21 27
20 21
19 20
34 35
33 34
32 33
31 32
30 31
30 36
29 30
28 29
44 45
43 44
42 43
42 46
41 42
40 41
39 40
38 39
37 38
53 54
52 53
51 52
50 51
50 55
49 50
49 56
48 49
47 48
64 65
63 ...

result:

ok Everything ok

Test #37:

score: 0
Accepted
time: 844ms
memory: 137920kb

input:

544133

output:

YES
515717
6 7
5 6
4 5
4 8
3 4
2 3
14 15
13 14
12 13
11 12
11 16
10 11
9 10
23 24
22 23
21 22
21 25
20 21
19 20
18 19
17 18
31 32
30 31
29 30
29 33
28 29
28 34
27 28
26 27
41 42
40 41
39 40
38 39
37 38
37 43
36 37
35 36
51 52
50 51
49 50
49 53
48 49
47 48
46 47
45 46
44 45
60 61
59 60
58 59
57 58
57...

result:

ok Everything ok

Test #38:

score: 0
Accepted
time: 777ms
memory: 135564kb

input:

276553

output:

YES
261516
6 7
5 6
4 5
4 8
3 4
2 3
14 15
13 14
12 13
11 12
11 16
10 11
9 10
23 24
22 23
21 22
21 25
20 21
19 20
18 19
17 18
31 32
30 31
29 30
29 33
28 29
28 34
27 28
26 27
41 42
40 41
39 40
38 39
37 38
37 43
36 37
35 36
51 52
50 51
49 50
49 53
48 49
47 48
46 47
45 46
44 45
60 61
59 60
58 59
57 58
57...

result:

ok Everything ok

Test #39:

score: 0
Accepted
time: 813ms
memory: 142140kb

input:

736904

output:

YES
699266
6 7
5 6
4 5
4 8
3 4
2 3
14 15
13 14
12 13
11 12
11 16
10 11
9 10
23 24
22 23
21 22
21 25
20 21
19 20
18 19
17 18
31 32
30 31
29 30
29 33
28 29
28 34
27 28
26 27
41 42
40 41
39 40
38 39
37 38
37 43
36 37
35 36
51 52
50 51
49 50
49 53
48 49
47 48
46 47
45 46
44 45
60 61
59 60
58 59
57 58
57...

result:

ok Everything ok

Test #40:

score: 0
Accepted
time: 860ms
memory: 142180kb

input:

1000000

output:

YES
949834
7 8
6 7
5 6
4 5
4 9
3 4
2 3
16 17
15 16
14 15
14 18
13 14
12 13
11 12
10 11
24 25
23 24
22 23
22 26
21 22
21 27
20 21
19 20
34 35
33 34
32 33
31 32
30 31
30 36
29 30
28 29
44 45
43 44
42 43
42 46
41 42
40 41
39 40
38 39
37 38
53 54
52 53
51 52
50 51
50 55
49 50
49 56
48 49
47 48
64 65
63 ...

result:

ok Everything ok

Extra Test:

score: 0
Extra Test Passed