QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#414503#8215. Isomorphic Delightucup-team1231#ML 265ms258088kbC++203.3kb2024-05-19 05:15:112024-05-19 05:15:13

Judging History

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

  • [2024-05-19 05:15:13]
  • 评测
  • 测评结果:ML
  • 用时:265ms
  • 内存:258088kb
  • [2024-05-19 05:15:11]
  • 提交

answer

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

vector<int> ch[4500005];
int siz[4500005];
int beg[5555], cnt, sz;

int arr[5555], len;
void gen_rooted(int sum, int pre) {
    if(sum == 0) {
        siz[cnt] = sz;
        // if(cnt%100000==0) cerr<<cnt<<"+\n";
        ch[cnt++] = vector<int>(arr, arr + len);
        return;
    }
    for(int i = pre + 1; i < cnt && siz[i] <= sum; i++) {
        if(siz[i] < sum && siz[i] > sum / 2) i = beg[sum];
        if(sum!=siz[i]&&(i==cnt-1||siz[i+1]+siz[i]>sum)) continue;
        arr[len++] = i;
        gen_rooted(sum - siz[i], i);
        len--;
    }
}

void output(int v) {
    putchar('(');
    for(auto u : ch[v]) output(u);
    putchar(')');
}
bool isok[4500005];
map<int,int> poo;
vector<int> goods[100055];
void init() {
    int N = 0;
    int pos = 0;
    for(sz = 1; sz<=22; sz++) {
        beg[sz] = cnt;
        gen_rooted(sz - 1, -1);
        // printf(" %d,%d\n", sz,N);
        for(int i = beg[sz]; i < cnt; i++) {
            assert(siz[i]>=siz[i-1]);
            bool ok = true;
            assert(is_sorted(ch[i].begin(),ch[i].end()));
            if(!ch[i].empty() && siz[ch[i].back()] > siz[i] / 2) ok = false;
            else if(!ch[i].empty() && siz[ch[i].back()] * 2 == siz[i]) {
                vector<int> vec(ch[i].begin(), ch[i].end() - 1);
                while(ch[pos] != vec) pos++;
                assert(ch[pos]==vec);
                // cerr<<pos<<","<<ch[i].back()<<"+\n";
                if(pos >= ch[i].back()) ok = false;
            }
            isok[i] = ok;
            if(isok[i]) {
                N += sz;
                goods[sz].push_back(i);
                poo[sz]++;
            }
        }
        cerr<<sz<<","<<cnt<<","<<N<<"+\n";
    }
}
#define SZ 1000999
pair<int,int> f[SZ];
int a[SZ];
void knapsack() {
    memset(a,-127/3,sizeof a);
    a[0]=0;
    for(auto g:poo) {
        auto pack=[&](int x,int y) {
            for(int u=SZ-1;u>=x*y;--u) {
                int v=a[u-x*y]+y;
                if(v<=a[u]) continue;
                a[u]=v;
                f[u]=make_pair(x,y);
            }
        };
        int x=g.first,y=g.second;
        for(int u=0;(1<<u)<=y;++u) {
            y-=1<<u;
            pack(x,1<<u);
        }
        pack(x,y);
    }
}
int main() {
    init();
    // cerr<<"++\n";

    int n;
    scanf("%d", &n);
    knapsack();
    if(n==6) {
printf(R"(YES
6
1 2
2 3
1 3
3 4
2 5
5 6)");
        return 0;
    }
    if(a[n]<0) {
        puts("NO");
        return 0;
    }
    map<int,int> cnt;
    int n_=n;
    while(n) {
        int x=f[n].first,y=f[n].second;
        cnt[x]+=y; n-=x*y;
    }
    printf("YES\n");
    int N=0;
    vector<pair<int,int>> eg;
    function<void(int,int)> dfs;
    dfs = [&] (int x,int fa) {
        int X=++N;
        if(fa) eg.push_back({N,fa});
        for(auto c:ch[x]) dfs(c,X);
    };
    for(auto g:cnt) {
        // cerr<<g.first<<"x"<<g.second<<"\n";
        auto&V=goods[g.first];
        while(g.second--) {
            assert(V.size());
            int x=V.back();
            dfs(x,0);
            V.pop_back();
        }
    }
    // cerr<<N<<"\n";
    assert(N==n_);
    printf("%d\n",int(eg.size()));
    for(auto e:eg) printf("%d %d\n",e.first,e.second);
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 231ms
memory: 257516kb

input:

1

output:

YES
0

result:

ok Everything ok

Test #2:

score: 0
Accepted
time: 249ms
memory: 257208kb

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: 242ms
memory: 257336kb

input:

4

output:

NO

result:

ok Everything ok

Test #4:

score: 0
Accepted
time: 226ms
memory: 257060kb

input:

2

output:

NO

result:

ok Everything ok

Test #5:

score: 0
Accepted
time: 233ms
memory: 257172kb

input:

3

output:

NO

result:

ok Everything ok

Test #6:

score: 0
Accepted
time: 234ms
memory: 257056kb

input:

5

output:

NO

result:

ok Everything ok

Test #7:

score: 0
Accepted
time: 256ms
memory: 257516kb

input:

7

output:

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

result:

ok Everything ok

Test #8:

score: 0
Accepted
time: 252ms
memory: 257240kb

input:

8

output:

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

result:

ok Everything ok

Test #9:

score: 0
Accepted
time: 249ms
memory: 257232kb

input:

9

output:

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

result:

ok Everything ok

Test #10:

score: 0
Accepted
time: 265ms
memory: 255212kb

input:

10

output:

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

result:

ok Everything ok

Test #11:

score: 0
Accepted
time: 231ms
memory: 257316kb

input:

11

output:

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

result:

ok Everything ok

Test #12:

score: 0
Accepted
time: 263ms
memory: 257500kb

input:

12

output:

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

result:

ok Everything ok

Test #13:

score: 0
Accepted
time: 244ms
memory: 257236kb

input:

13

output:

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

result:

ok Everything ok

Test #14:

score: 0
Accepted
time: 246ms
memory: 257572kb

input:

14

output:

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

result:

ok Everything ok

Test #15:

score: 0
Accepted
time: 261ms
memory: 257184kb

input:

15

output:

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

result:

ok Everything ok

Test #16:

score: 0
Accepted
time: 251ms
memory: 257408kb

input:

16

output:

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

result:

ok Everything ok

Test #17:

score: 0
Accepted
time: 261ms
memory: 255444kb

input:

17

output:

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

result:

ok Everything ok

Test #18:

score: 0
Accepted
time: 243ms
memory: 255280kb

input:

18

output:

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

result:

ok Everything ok

Test #19:

score: 0
Accepted
time: 211ms
memory: 257316kb

input:

19

output:

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

result:

ok Everything ok

Test #20:

score: 0
Accepted
time: 243ms
memory: 257512kb

input:

598

output:

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

result:

ok Everything ok

Test #21:

score: 0
Accepted
time: 237ms
memory: 257232kb

input:

245

output:

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

result:

ok Everything ok

Test #22:

score: 0
Accepted
time: 239ms
memory: 255268kb

input:

793

output:

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

result:

ok Everything ok

Test #23:

score: 0
Accepted
time: 242ms
memory: 257184kb

input:

133

output:

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

result:

ok Everything ok

Test #24:

score: 0
Accepted
time: 241ms
memory: 257456kb

input:

681

output:

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

result:

ok Everything ok

Test #25:

score: 0
Accepted
time: 260ms
memory: 255160kb

input:

922

output:

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

result:

ok Everything ok

Test #26:

score: 0
Accepted
time: 246ms
memory: 257516kb

input:

876

output:

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

result:

ok Everything ok

Test #27:

score: 0
Accepted
time: 246ms
memory: 257232kb

input:

7740

output:

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

result:

ok Everything ok

Test #28:

score: 0
Accepted
time: 256ms
memory: 257232kb

input:

2460

output:

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

result:

ok Everything ok

Test #29:

score: 0
Accepted
time: 259ms
memory: 255480kb

input:

7533

output:

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

result:

ok Everything ok

Test #30:

score: 0
Accepted
time: 250ms
memory: 257208kb

input:

5957

output:

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

result:

ok Everything ok

Test #31:

score: 0
Accepted
time: 259ms
memory: 258064kb

input:

92651

output:

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

result:

ok Everything ok

Test #32:

score: 0
Accepted
time: 252ms
memory: 257596kb

input:

58779

output:

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

result:

ok Everything ok

Test #33:

score: 0
Accepted
time: 245ms
memory: 257380kb

input:

12203

output:

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

result:

ok Everything ok

Test #34:

score: 0
Accepted
time: 232ms
memory: 257732kb

input:

55627

output:

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

result:

ok Everything ok

Test #35:

score: 0
Accepted
time: 262ms
memory: 258088kb

input:

99051

output:

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

result:

ok Everything ok

Test #36:

score: -100
Memory Limit Exceeded

input:

811713

output:

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

result: