QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#414495#8215. Isomorphic Delightucup-team1231#WA 181ms121716kbC++203.1kb2024-05-19 04:32:232024-05-19 04:32:25

Judging History

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

  • [2024-05-19 04:32:25]
  • 评测
  • 测评结果:WA
  • 用时:181ms
  • 内存:121716kb
  • [2024-05-19 04:32:23]
  • 提交

answer

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

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

int arr[5555], len;
void gen_rooted(int sum, int pre) {
    if(sum == 0) {
        siz[cnt] = sz;
        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[3000005];
map<int,int> poo;
vector<int> goods[100055];
void init() {
    int N = 0;
    int pos = 0;
    for(sz = 1; sz<=21; sz++) {
        beg[sz] = cnt;
        gen_rooted(sz - 1, -1);
        // printf(" %d,%d\n", sz,N);
        for(int i = beg[sz]; i < cnt; i++) {
            bool ok = true;
            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++;
                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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 173ms
memory: 121440kb

input:

1

output:

YES
0

result:

ok Everything ok

Test #2:

score: 0
Accepted
time: 145ms
memory: 121656kb

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: 157ms
memory: 119248kb

input:

4

output:

NO

result:

ok Everything ok

Test #4:

score: 0
Accepted
time: 167ms
memory: 120052kb

input:

2

output:

NO

result:

ok Everything ok

Test #5:

score: 0
Accepted
time: 168ms
memory: 121324kb

input:

3

output:

NO

result:

ok Everything ok

Test #6:

score: 0
Accepted
time: 164ms
memory: 121328kb

input:

5

output:

NO

result:

ok Everything ok

Test #7:

score: 0
Accepted
time: 161ms
memory: 121416kb

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: 181ms
memory: 121704kb

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: 159ms
memory: 119656kb

input:

9

output:

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

result:

ok Everything ok

Test #10:

score: 0
Accepted
time: 174ms
memory: 121512kb

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: 151ms
memory: 121440kb

input:

11

output:

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

result:

ok Everything ok

Test #12:

score: 0
Accepted
time: 146ms
memory: 121412kb

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: 164ms
memory: 121716kb

input:

13

output:

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

result:

ok Everything ok

Test #14:

score: 0
Accepted
time: 155ms
memory: 121460kb

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: 154ms
memory: 121460kb

input:

15

output:

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

result:

ok Everything ok

Test #16:

score: 0
Accepted
time: 150ms
memory: 121456kb

input:

16

output:

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

result:

ok Everything ok

Test #17:

score: -100
Wrong Answer
time: 175ms
memory: 121412kb

input:

17

output:

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

result:

wrong answer Not asymmetric