QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#323258#8215. Isomorphic DelightkarunaAC ✓67ms25652kbC++202.4kb2024-02-09 01:37:422024-02-09 01:37:42

Judging History

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

  • [2024-02-09 01:37:42]
  • 评测
  • 测评结果:AC
  • 用时:67ms
  • 内存:25652kb
  • [2024-02-09 01:37:42]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

const int SZ = 21;

vector<vector<pair<int, int>>> R[SZ + 1]; // rooted trees
vector<vector<pair<int, int>>> T[SZ + 1]; // non-rooted

vector<pair<int, int>> E;

void f(int n, int s, int m, int j, bool h) {
	if (s == n) {
		if (!h) R[n].push_back(E);
		else T[n].push_back(E);
		return;
	}
	assert(n - s >= m);
	if (n - s < 2 * m) {
		if (m != n - s) j = 0;
		m = n - s;
	}
	if (h && m >= (n + 1) / 2) return;

	// don't use m
	if (s + m + 1 <= n)
		f(n, s, m + 1, 0, h);

	// use m
	for (int k = j; k < R[m].size(); k++) {
		E.push_back({ 1, s + 1 });
		for (auto [u, v] : R[m][k]) {
			E.push_back({ s + u, s + v });
		}

		f(n, s + m, m, k + 1, h);

		for (int l = 0; l < m; l++) E.pop_back();
	}
}

void generate(int n) {
	if (n <= 10) f(n, 1, 1, 0, false);
	f(n, 1, 1, 0, true);
	if (n % 2 == 0) {
		for (int i = 0; i < R[n / 2].size(); i++) for (int j = 0; j < i; j++) {
			vector<pair<int, int>> E;
			E.push_back({ 1, n / 2 + 1 });
			for (auto [u, v] : R[n / 2][i]) E.push_back({ u, v });
			for (auto [u, v] : R[n / 2][j]) E.push_back({ n / 2 + u, n / 2 + v });
			T[n].push_back(E);
		}
	}
}
int main() {
	for (int n = 1; n <= SZ; n++) {
		generate(n);
	}

	int n;
	cin >> n;

	if (n == 1) {
		cout << "YES\n";
		cout << 0 << '\n';
	}
	else if (n <= 5) {
		cout << "NO\n";
	}
	else if (n <= 7) {
		cout << "YES\n";
		cout << 6 << '\n';
		cout << "1 2\n";
		cout << "2 3\n";
		cout << "3 1\n";
		cout << "1 4\n";
		cout << "2 5\n";
		cout << "5 6\n";
	}
	else {
		int m = 7, p = 0, s = 1;
		vector<pair<int, int>> V;
		while (s != n) {
			while (p == T[m].size()) {
				++m;
				p = 0;
			}
			bool f = false;
			if (s + m + (p + 1 == T[m].size() ? m + 1 : m) > n) {
				f = true;
			}
			if (s + m == n) f = false;
			if (!f) {
				//cout << m << ' ';
				for (auto [u, v] : T[m][p]) {
					V.push_back({ s + u, s + v });
				}
				++p;
				s += m;
			}
			else {
				//cout << n - s << endl;
				V.push_back({ s + 1, s + 2 });
				V.push_back({ s + 1, s + 3 });
				V.push_back({ s + 3, s + 4 });
				V.push_back({ s + 1, s + 5 });
				for (int i = 6; i <= n - s; i++) {
					V.push_back({ s + i - 1, s + i });
				}
				break;
			}
		}
		cout << "YES\n";
		cout << V.size() << '\n';
		for (auto [u, v] : V) {
			cout << u << ' ' << v << '\n';
		}
	}
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 8ms
memory: 15516kb

input:

1

output:

YES
0

result:

ok Everything ok

Test #2:

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

input:

6

output:

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

result:

ok Everything ok

Test #3:

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

input:

4

output:

NO

result:

ok Everything ok

Test #4:

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

input:

2

output:

NO

result:

ok Everything ok

Test #5:

score: 0
Accepted
time: 7ms
memory: 15620kb

input:

3

output:

NO

result:

ok Everything ok

Test #6:

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

input:

5

output:

NO

result:

ok Everything ok

Test #7:

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

input:

7

output:

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

result:

ok Everything ok

Test #8:

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

input:

8

output:

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

result:

ok Everything ok

Test #9:

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

input:

9

output:

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

result:

ok Everything ok

Test #10:

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

input:

10

output:

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

result:

ok Everything ok

Test #11:

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

input:

11

output:

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

result:

ok Everything ok

Test #12:

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

input:

12

output:

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

result:

ok Everything ok

Test #13:

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

input:

13

output:

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

result:

ok Everything ok

Test #14:

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

input:

14

output:

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

result:

ok Everything ok

Test #15:

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

input:

15

output:

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

result:

ok Everything ok

Test #16:

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

input:

16

output:

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

result:

ok Everything ok

Test #17:

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

input:

17

output:

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

result:

ok Everything ok

Test #18:

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

input:

18

output:

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

result:

ok Everything ok

Test #19:

score: 0
Accepted
time: 7ms
memory: 15360kb

input:

19

output:

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

result:

ok Everything ok

Test #20:

score: 0
Accepted
time: 7ms
memory: 15552kb

input:

598

output:

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

result:

ok Everything ok

Test #21:

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

input:

245

output:

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

result:

ok Everything ok

Test #22:

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

input:

793

output:

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

result:

ok Everything ok

Test #23:

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

input:

133

output:

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

result:

ok Everything ok

Test #24:

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

input:

681

output:

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

result:

ok Everything ok

Test #25:

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

input:

922

output:

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

result:

ok Everything ok

Test #26:

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

input:

876

output:

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

result:

ok Everything ok

Test #27:

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

input:

7740

output:

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

result:

ok Everything ok

Test #28:

score: 0
Accepted
time: 7ms
memory: 15536kb

input:

2460

output:

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

result:

ok Everything ok

Test #29:

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

input:

7533

output:

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

result:

ok Everything ok

Test #30:

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

input:

5957

output:

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

result:

ok Everything ok

Test #31:

score: 0
Accepted
time: 11ms
memory: 17188kb

input:

92651

output:

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

result:

ok Everything ok

Test #32:

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

input:

58779

output:

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

result:

ok Everything ok

Test #33:

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

input:

12203

output:

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

result:

ok Everything ok

Test #34:

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

input:

55627

output:

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

result:

ok Everything ok

Test #35:

score: 0
Accepted
time: 15ms
memory: 17364kb

input:

99051

output:

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

result:

ok Everything ok

Test #36:

score: 0
Accepted
time: 60ms
memory: 25412kb

input:

811713

output:

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

result:

ok Everything ok

Test #37:

score: 0
Accepted
time: 38ms
memory: 22524kb

input:

544133

output:

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

result:

ok Everything ok

Test #38:

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

input:

276553

output:

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

result:

ok Everything ok

Test #39:

score: 0
Accepted
time: 65ms
memory: 24736kb

input:

736904

output:

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

result:

ok Everything ok

Test #40:

score: 0
Accepted
time: 67ms
memory: 25652kb

input:

1000000

output:

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

result:

ok Everything ok

Extra Test:

score: 0
Extra Test Passed