QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#320959#8215. Isomorphic Delightucup-team296#WA 5ms13012kbC++144.5kb2024-02-04 00:55:362024-02-04 00:55:36

Judging History

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

  • [2024-02-04 00:55:36]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:13012kb
  • [2024-02-04 00:55:36]
  • 提交

answer

#include <bits/stdc++.h>

#define long long long int
#define DEBUG
using namespace std;

// @author: pashka

struct tree {
    int n;
    vector<int> p;

    tree(int _n) {
        n = _n;
        p.assign(n, -1);
    }
};

int MAX = 15;
vector<vector<tree>> all_trees;

void build_all(vector<tree> &here, int n, int k) {
    if (n == 1) {
        here.push_back({1});
        return;
    }
    if (k <= 0) return;
    build_all(here, n, k - 1);
    for (int x = 1; x * k <= n - 1; x++) {
        int nn = all_trees[k].size();
        if (x > nn) continue;
        vector<int> ind(x);
        for (int i = 0; i < x; i++) ind[i] = i;

        vector<tree> sm;
        build_all(sm, n - x * k, k - 1);

        while (true) {

            for (auto &t: sm) {
                tree tt(n);
                for (int i = 0; i < n - x * k; i++) {
                    tt.p[i] = t.p[i];
                }
                int nn2 = n - x * k;
                for (int j: ind) {
                    tree &t2 = all_trees[k][j];
                    tt.p[nn2] = 0;
                    for (int i = 1; i < k; i++) {
                        tt.p[nn2 + i] = t2.p[i] + nn2;
                    }
                    nn2 += k;
                }
                here.push_back(tt);
            }

            int j = x - 1;
            while (j >= 0 && ind[j] == nn - x + j) {
                j--;
            }
            if (j < 0) break;
            ind[j]++;
            for (int w = j + 1; w < x; w++) {
                ind[w] = ind[w - 1] + 1;
            }
//            for (int xx: ind) cout << xx << " ";
//            cout << "\n";
        }
    }
}

vector<vector<tree>> all_unrooted;

void precalc() {
    all_trees.resize(MAX + 1);
    for (int n = 1; n <= MAX; n++) {
        build_all(all_trees[n], n, n);
//        cout << n << ": " << all_trees[n].size() << "\n";
    }
    all_unrooted.resize(2 * MAX + 1);
    for (int n = 1; n <= 21; n++) {
        build_all(all_unrooted[n], n, (n - 1) / 2);
        if (n % 2 == 0) {
            int nn = all_trees[n / 2].size();
            for (int i = 0; i < nn; i++) {
                for (int j = i + 1; j < nn; j++) {
                    tree tt(n);
                    tree &t1 = all_trees[n / 2][i];
                    tree &t2 = all_trees[n / 2][j];
                    for (int x = 0; x < n / 2; x++) {
                        tt.p[x] = t1.p[x];
                        tt.p[n / 2 + x] = t2.p[x] + n / 2;
                    }
                    tt.p[n / 2] = 0;
                    all_unrooted[n].push_back(tt);
                }
            }
        }
//        cout << n << " " << all_unrooted[n].size() << "\n";
    }
}

int nn = 0;
vector<pair<int, int>> res;

void print_tree(tree &t) {
    int n = t.n;
    for (int i = 1; i < n; i++) {
        res.emplace_back(t.p[i] + 1 + nn, i + 1 + nn);
    }
    nn += n;
}

int main() {
    ios::sync_with_stdio(false);

    precalc();
    int n;
    cin >> n;
    if (n == 1) {
        cout << "YES\n0\n";
        return 0;
    }
    if (n < 6) {
        cout << "NO\n";
    }
    if (n == 6) {
        cout << "YES\n0\n";
        cout << "6\n";
        cout << "1 2\n";
        cout << "2 3\n";
        cout << "1 3\n";
        cout << "3 4\n";
        cout << "2 5\n";
        cout << "5 6\n";
        return 0;
    }
    if (n == 7) {
        print_tree(all_unrooted[7][0]);
    } else {
        nn = 1;
        for (int i = 7; ; i++) {
            int u = all_unrooted[i].size();
            for (int j = 0; j < u; j++) {
                int next_size = j + 1 == u ? i + 1 : i;
                if (nn + i + next_size <= n) {
                    print_tree(all_unrooted[i][j]);
                } else if (nn + i == n) {
                    print_tree(all_unrooted[i][j]);
                    break;
                } else {
                    res.emplace_back(nn + 1, nn + 2);
                    res.emplace_back(nn + 1, nn + 3);
                    res.emplace_back(nn + 3, nn + 4);
                    res.emplace_back(nn + 1, nn + 5);
                    for (int j = nn + 6; j <= n; j++) {
                        res.emplace_back(j - 1, j);
                    }
                    nn = n;
                    break;
                }
            }
            if (nn == n) break;
        }
    }

    cout << "YES\n";
    cout << res.size() << "\n";
    for (auto &p : res) {
        cout << p.first << " " << p.second << "\n";
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 13012kb

input:

1

output:

YES
0

result:

ok Everything ok

Test #2:

score: -100
Wrong Answer
time: 5ms
memory: 12792kb

input:

6

output:

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

result:

wrong answer Not asymmetric