QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#344687#8215. Isomorphic DelightSolitaryDream#AC ✓93ms24960kbC++172.6kb2024-03-04 21:23:482024-03-04 21:23:48

Judging History

This is the latest submission verdict.

  • [2024-03-04 21:23:48]
  • Judged
  • Verdict: AC
  • Time: 93ms
  • Memory: 24960kb
  • [2024-03-04 21:23:48]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
int n;
struct Graph {
    int n;
    vector<pii> g;
    void Debug() {
        cout << n << endl;
        for (auto [x, y] : g) cout << x << ' ' << y << endl;
    }
};
void MergeTo(Graph &a, const Graph &b) {
    for (const auto [x, y] : b.g) {
        a.g.push_back({x + a.n, y + a.n});
    }
    a.n += b.n;
}
vector<Graph> f[100];
typedef vector<Graph>::iterator vgit;
inline void Dfs(int si, vgit it, Graph cur, int target_size, int size_limit, vector<Graph> &rst) {
    if (cur.n == target_size) { rst.push_back(cur); return; }
    if (it == f[si].end()) it = f[++si].begin();
    if (cur.n + si > target_size || si > size_limit) return;
    Dfs(si, next(it), cur, target_size, size_limit, rst);
    cur.g.push_back({1, cur.n + 1});
    MergeTo(cur, *it);
    Dfs(si, next(it), cur, target_size, size_limit, rst);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    if (n == 1) { cout << "YES\n0\n"; return 0; }
    if (n <= 5) { cout << "NO\n"; return 0; }
    if (n <= 7) { 
        cout << "YES\n6\n1 2\n2 3\n1 3\n3 4\n2 5\n5 6\n";
        return 0;
    }
    f[1].push_back({1, {}});
    Graph ans({0, {}});
    MergeTo(ans, f[1][0]);
    const int LIM = 16;
    for (int i = 2; i <= LIM; ++i) {
        Dfs(1, f[1].begin(), {1, {}}, i, 1e9, f[i]);
        // for (auto x : f[i]) x.Debug();
    }
    for (int i = 7; i <= 2 * LIM; ++i) {
        vector<Graph> rst;
        if (i % 2 == 0) {
            for (vgit p1 = f[i / 2].begin(); p1 != f[i / 2].end(); ++p1) 
                for (vgit p2 = next(p1); p2 != f[i / 2].end(); ++p2) {
                    Graph cur(*p1);
                    cur.g.push_back({1, cur.n + 1});
                    MergeTo(cur, *p2);
                    rst.push_back(cur);
                }
        }
        Dfs(1, f[1].begin(), {1, {}}, i, (i - 1) / 2, rst);
        // cout << rst.size() << endl;
        while (!rst.empty()) {
            int nxt = (rst.size() >= 2 ? i : i + 1);
            if (ans.n + i + nxt > n) break;
            MergeTo(ans, rst.back());
            rst.pop_back();
        }
        if (!rst.empty()) break;
    }
    Graph last;
    last.n = n - ans.n;
    // cout << last.n << endl;
    // return 0;
    last.g.push_back({1, 2});
    last.g.push_back({1, 3});
    last.g.push_back({3, 4});
    last.g.push_back({1, 5});
    for (int i = 6; i <= last.n; ++i) last.g.push_back({i - 1, i});
    MergeTo(ans, last);
    cout << "YES\n";
    cout << ans.g.size() << '\n';
    for (auto [x, y] : ans.g) cout << x << ' ' << y << '\n'; 
    return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3604kb

input:

1

output:

YES
0

result:

ok Everything ok

Test #2:

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

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

input:

4

output:

NO

result:

ok Everything ok

Test #4:

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

input:

2

output:

NO

result:

ok Everything ok

Test #5:

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

input:

3

output:

NO

result:

ok Everything ok

Test #6:

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

input:

5

output:

NO

result:

ok Everything ok

Test #7:

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

input:

7

output:

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

result:

ok Everything ok

Test #8:

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

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

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

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: 9ms
memory: 9584kb

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: 9ms
memory: 9628kb

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

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

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

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

input:

16

output:

YES
13
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

result:

ok Everything ok

Test #17:

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

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: 9ms
memory: 9592kb

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

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

input:

598

output:

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

result:

ok Everything ok

Test #21:

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

input:

245

output:

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

result:

ok Everything ok

Test #22:

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

input:

793

output:

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

result:

ok Everything ok

Test #23:

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

input:

133

output:

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

result:

ok Everything ok

Test #24:

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

input:

681

output:

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

result:

ok Everything ok

Test #25:

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

input:

922

output:

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

result:

ok Everything ok

Test #26:

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

input:

876

output:

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

result:

ok Everything ok

Test #27:

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

input:

7740

output:

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

result:

ok Everything ok

Test #28:

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

input:

2460

output:

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

result:

ok Everything ok

Test #29:

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

input:

7533

output:

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

result:

ok Everything ok

Test #30:

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

input:

5957

output:

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

result:

ok Everything ok

Test #31:

score: 0
Accepted
time: 14ms
memory: 11172kb

input:

92651

output:

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

result:

ok Everything ok

Test #32:

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

input:

58779

output:

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

result:

ok Everything ok

Test #33:

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

input:

12203

output:

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

result:

ok Everything ok

Test #34:

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

input:

55627

output:

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

result:

ok Everything ok

Test #35:

score: 0
Accepted
time: 14ms
memory: 11296kb

input:

99051

output:

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

result:

ok Everything ok

Test #36:

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

input:

811713

output:

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

result:

ok Everything ok

Test #37:

score: 0
Accepted
time: 50ms
memory: 17980kb

input:

544133

output:

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

result:

ok Everything ok

Test #38:

score: 0
Accepted
time: 20ms
memory: 14736kb

input:

276553

output:

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

result:

ok Everything ok

Test #39:

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

input:

736904

output:

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

result:

ok Everything ok

Test #40:

score: 0
Accepted
time: 93ms
memory: 24844kb

input:

1000000

output:

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

result:

ok Everything ok

Extra Test:

score: 0
Extra Test Passed