QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#334938 | #8215. Isomorphic Delight | ucup-team1209# | RE | 0ms | 0kb | C++20 | 3.2kb | 2024-02-22 15:21:09 | 2024-02-22 15:21:09 |
answer
#include<bits/stdc++.h>
using std::cin;
using std::cout;
using pr = std::pair<int, int>;
using u64 = unsigned long long;
const u64 C = 12894718241;
u64 f(u64 x) {
x ^= x << 13;
x ^= x >> 7;
x ^= x << 17;
return x;
}
std::vector<pr> edge;
const int N = 3000005;
std::vector<int> son[N];
void cyctree(int n, int base = 0) {
for(int i = 2;i <= n - 3;++i) {
edge.emplace_back(base + i, base + i - 1);
}
edge.emplace_back(base + 1, base + n - 3);
edge.emplace_back(base + 1, base + n - 2);
edge.emplace_back(base + 2, base + n - 1);
edge.emplace_back(base + n - 1, base + n);
}
int tct;
int tree(int x) {
int p = ++tct;
for(int z : son[x]) {
edge.emplace_back(p, tree(z));
}
return p;
}
u64 hash[N];
int size[N];
int ed[N];
int cc;
int n;
int okcc = 0;
std::map<std::vector<u64>, int> map;
void hashset(int x) {
if(son[x].size() > 1) return ;
std::vector<u64> hashs;
auto dfs = [&](int x, u64 ancv, auto dfs) -> void {
hashs.push_back(hash[x] + ancv);
for(int i : son[x]) {
dfs(i, f(hash[x] + ancv - f(hash[i])), dfs);
}
};
dfs(x, 0, dfs);
sort(hashs.begin(), hashs.end());
for(int i = 1;i < (int) hashs.size();++i) {
if(hashs[i] == hashs[i - 1]) {
return ;
}
}
okcc += hashs.size();
map[hashs] = x;
}
int main() {
std::ios::sync_with_stdio(false), cin.tie(0);
size[1] = 1, hash[1] = C, ed[1] = 1, cc = 1;
hashset(1);
const int M = 21;
for(int i = 2;i <= M;++i) {
std::vector<int> s;
auto dfs = [&](int rem, int idx, auto & s, auto dfs) {
if(rem == 0) {
size[++cc] = i;
hash[cc] += C;
son[cc] = s;
for(int x : s) {
hash[cc] += f(hash[x]);
}
hashset(cc);
return ;
}
idx = std::min(idx, ed[rem]);
for(int i = idx;i >= 1;--i) {
s.push_back(i);
dfs(rem - size[i], i - 1, s, dfs);
s.pop_back();
}
};
dfs(i - 1, 1e9, s, dfs);
ed[i] = cc;
}
std::vector<std::pair<int, int>> vecs;
for(auto & [a, b] : map) {
vecs.emplace_back(size[b], b);
}
sort(vecs.begin(), vecs.end());
auto greedy = [&](int n) {
std::vector<int> v;
for(int i = 1;n;++i) {
if(vecs[i].first <= n) {
v.push_back(vecs[i].second);
n -= vecs[i].first;
} else {
if(size[v[0]] < vecs[i].first) {
for(int j = 0;j < (int) v.size();++j) {
const int sub = vecs[i].first - size[v[j]];
if(sub <= n) {
n -= sub;
v.erase(v.begin() + j);
v.push_back(vecs[i].second);
break;
}
}
}
}
}
return v;
};
std::vector<int> ans;
for(int idx = 0;idx < 2;++idx) {
std::vector<int> v;
}
cin >> n;
auto A = greedy(n);
if(n >= 7 || n == 1) {
auto B = greedy(n - 1); B.push_back(1);
if(B.size() > A.size()) {
A = B;
}
}
int cyc_size = n;
for(int x : A) cyc_size -= size[x];
if(cyc_size >= 6 || cyc_size == 0) {
cout << "YES" << '\n';
if(cyc_size) cyctree(tct = cyc_size);
for(auto x : A) {
tree(x);
}
cout << edge.size() << '\n';
for(auto [a, b] : edge) {
cout << a << ' ' << b << '\n';
}
} else {
cout << "NO" << '\n';
}
// cin >> n;
}
/*
14
YES
12
2 1
3 2
1 3
1 4
2 5
5 6
11 12
10 11
9 10
9 13
8 9
7 8
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
1