QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#334945 | #8215. Isomorphic Delight | ucup-team1209# | AC ✓ | 875ms | 142192kb | C++20 | 3.2kb | 2024-02-22 15:25:07 | 2024-02-22 15:25:07 |
Judging History
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) {
if(v.empty() && n <= 6) return 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, {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
*/
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 781ms
memory: 133392kb
input:
1
output:
YES 0
result:
ok Everything ok
Test #2:
score: 0
Accepted
time: 793ms
memory: 133524kb
input:
6
output:
YES 6 2 1 3 2 1 3 1 4 2 5 5 6
result:
ok Everything ok
Test #3:
score: 0
Accepted
time: 810ms
memory: 133640kb
input:
4
output:
NO
result:
ok Everything ok
Test #4:
score: 0
Accepted
time: 773ms
memory: 133300kb
input:
2
output:
NO
result:
ok Everything ok
Test #5:
score: 0
Accepted
time: 793ms
memory: 133340kb
input:
3
output:
NO
result:
ok Everything ok
Test #6:
score: 0
Accepted
time: 798ms
memory: 133304kb
input:
5
output:
NO
result:
ok Everything ok
Test #7:
score: 0
Accepted
time: 796ms
memory: 133484kb
input:
7
output:
YES 6 5 6 4 5 3 4 3 7 2 3 1 2
result:
ok Everything ok
Test #8:
score: 0
Accepted
time: 793ms
memory: 133476kb
input:
8
output:
YES 6 6 7 5 6 4 5 4 8 3 4 2 3
result:
ok Everything ok
Test #9:
score: 0
Accepted
time: 771ms
memory: 133472kb
input:
9
output:
YES 7 7 8 6 7 5 6 4 5 4 9 3 4 2 3
result:
ok Everything ok
Test #10:
score: 0
Accepted
time: 774ms
memory: 133480kb
input:
10
output:
YES 8 8 9 7 8 6 7 6 10 5 6 4 5 3 4 2 3
result:
ok Everything ok
Test #11:
score: 0
Accepted
time: 774ms
memory: 133416kb
input:
11
output:
YES 9 9 10 8 9 7 8 7 11 6 7 5 6 4 5 3 4 2 3
result:
ok Everything ok
Test #12:
score: 0
Accepted
time: 756ms
memory: 133596kb
input:
12
output:
YES 10 10 11 9 10 8 9 8 12 7 8 6 7 5 6 4 5 3 4 2 3
result:
ok Everything ok
Test #13:
score: 0
Accepted
time: 774ms
memory: 133644kb
input:
13
output:
YES 11 10 11 9 10 8 9 8 12 7 8 7 13 6 7 5 6 4 5 3 4 2 3
result:
ok Everything ok
Test #14:
score: 0
Accepted
time: 772ms
memory: 133400kb
input:
14
output:
YES 12 10 11 9 10 8 9 8 12 7 8 6 7 6 13 5 6 5 14 4 5 3 4 2 3
result:
ok Everything ok
Test #15:
score: 0
Accepted
time: 737ms
memory: 133628kb
input:
15
output:
YES 13 5 6 4 5 3 4 3 7 2 3 1 2 13 14 12 13 11 12 10 11 10 15 9 10 8 9
result:
ok Everything ok
Test #16:
score: 0
Accepted
time: 749ms
memory: 133596kb
input:
16
output:
YES 13 6 7 5 6 4 5 4 8 3 4 2 3 14 15 13 14 12 13 11 12 11 16 10 11 9 10
result:
ok Everything ok
Test #17:
score: 0
Accepted
time: 771ms
memory: 133520kb
input:
17
output:
YES 14 6 7 5 6 4 5 4 8 3 4 2 3 15 16 14 15 13 14 13 17 12 13 11 12 10 11 9 10
result:
ok Everything ok
Test #18:
score: 0
Accepted
time: 781ms
memory: 133500kb
input:
18
output:
YES 15 7 8 6 7 5 6 4 5 4 9 3 4 2 3 16 17 15 16 14 15 14 18 13 14 12 13 11 12 10 11
result:
ok Everything ok
Test #19:
score: 0
Accepted
time: 762ms
memory: 133480kb
input:
19
output:
YES 16 8 9 7 8 6 7 6 10 5 6 4 5 3 4 2 3 16 17 15 16 14 15 14 18 13 14 13 19 12 13 11 12
result:
ok Everything ok
Test #20:
score: 0
Accepted
time: 797ms
memory: 133480kb
input:
598
output:
YES 544 7 8 6 7 5 6 4 5 4 9 3 4 2 3 16 17 15 16 14 15 14 18 13 14 12 13 11 12 10 11 24 25 23 24 22 23 22 26 21 22 21 27 20 21 19 20 34 35 33 34 32 33 31 32 30 31 30 36 29 30 28 29 44 45 43 44 42 43 42 46 41 42 40 41 39 40 38 39 37 38 53 54 52 53 51 52 50 51 50 55 49 50 49 56 48 49 47 48 64 65 63 64 ...
result:
ok Everything ok
Test #21:
score: 0
Accepted
time: 816ms
memory: 133396kb
input:
245
output:
YES 221 5 6 4 5 3 4 3 7 2 3 1 2 13 14 12 13 11 12 10 11 10 15 9 10 8 9 22 23 21 22 20 21 20 24 19 20 18 19 17 18 16 17 30 31 29 30 28 29 28 32 27 28 27 33 26 27 25 26 40 41 39 40 38 39 37 38 36 37 36 42 35 36 34 35 50 51 49 50 48 49 48 52 47 48 46 47 45 46 44 45 43 44 59 60 58 59 57 58 56 57 56 61 5...
result:
ok Everything ok
Test #22:
score: 0
Accepted
time: 806ms
memory: 133500kb
input:
793
output:
YES 724 7 8 6 7 5 6 4 5 4 9 3 4 2 3 16 17 15 16 14 15 14 18 13 14 12 13 11 12 10 11 24 25 23 24 22 23 22 26 21 22 21 27 20 21 19 20 34 35 33 34 32 33 31 32 30 31 30 36 29 30 28 29 44 45 43 44 42 43 42 46 41 42 40 41 39 40 38 39 37 38 53 54 52 53 51 52 50 51 50 55 49 50 49 56 48 49 47 48 64 65 63 64 ...
result:
ok Everything ok
Test #23:
score: 0
Accepted
time: 760ms
memory: 133612kb
input:
133
output:
YES 119 8 9 7 8 6 7 6 10 5 6 4 5 3 4 2 3 16 17 15 16 14 15 14 18 13 14 13 19 12 13 11 12 26 27 25 26 24 25 23 24 22 23 22 28 21 22 20 21 35 36 34 35 33 34 32 33 32 37 31 32 31 38 30 31 29 30 46 47 45 46 44 45 43 44 42 43 41 42 41 48 40 41 39 40 55 56 54 55 53 54 53 57 52 53 51 52 51 58 50 51 49 50 6...
result:
ok Everything ok
Test #24:
score: 0
Accepted
time: 771ms
memory: 133644kb
input:
681
output:
YES 620 6 7 5 6 4 5 4 8 3 4 2 3 14 15 13 14 12 13 11 12 11 16 10 11 9 10 23 24 22 23 21 22 21 25 20 21 19 20 18 19 17 18 31 32 30 31 29 30 29 33 28 29 28 34 27 28 26 27 41 42 40 41 39 40 38 39 37 38 37 43 36 37 35 36 51 52 50 51 49 50 49 53 48 49 47 48 46 47 45 46 44 45 60 61 59 60 58 59 57 58 57 62...
result:
ok Everything ok
Test #25:
score: 0
Accepted
time: 762ms
memory: 133492kb
input:
922
output:
YES 843 7 8 6 7 5 6 4 5 4 9 3 4 2 3 16 17 15 16 14 15 14 18 13 14 12 13 11 12 10 11 24 25 23 24 22 23 22 26 21 22 21 27 20 21 19 20 34 35 33 34 32 33 31 32 30 31 30 36 29 30 28 29 44 45 43 44 42 43 42 46 41 42 40 41 39 40 38 39 37 38 53 54 52 53 51 52 50 51 50 55 49 50 49 56 48 49 47 48 64 65 63 64 ...
result:
ok Everything ok
Test #26:
score: 0
Accepted
time: 808ms
memory: 133564kb
input:
876
output:
YES 800 6 7 5 6 4 5 4 8 3 4 2 3 14 15 13 14 12 13 11 12 11 16 10 11 9 10 23 24 22 23 21 22 21 25 20 21 19 20 18 19 17 18 31 32 30 31 29 30 29 33 28 29 28 34 27 28 26 27 41 42 40 41 39 40 38 39 37 38 37 43 36 37 35 36 51 52 50 51 49 50 49 53 48 49 47 48 46 47 45 46 44 45 60 61 59 60 58 59 57 58 57 62...
result:
ok Everything ok
Test #27:
score: 0
Accepted
time: 802ms
memory: 133648kb
input:
7740
output:
YES 7191 6 7 5 6 4 5 4 8 3 4 2 3 14 15 13 14 12 13 11 12 11 16 10 11 9 10 23 24 22 23 21 22 21 25 20 21 19 20 18 19 17 18 31 32 30 31 29 30 29 33 28 29 28 34 27 28 26 27 41 42 40 41 39 40 38 39 37 38 37 43 36 37 35 36 51 52 50 51 49 50 49 53 48 49 47 48 46 47 45 46 44 45 60 61 59 60 58 59 57 58 57 6...
result:
ok Everything ok
Test #28:
score: 0
Accepted
time: 860ms
memory: 133520kb
input:
2460
output:
YES 2268 7 8 6 7 5 6 4 5 4 9 3 4 2 3 16 17 15 16 14 15 14 18 13 14 12 13 11 12 10 11 24 25 23 24 22 23 22 26 21 22 21 27 20 21 19 20 34 35 33 34 32 33 31 32 30 31 30 36 29 30 28 29 44 45 43 44 42 43 42 46 41 42 40 41 39 40 38 39 37 38 53 54 52 53 51 52 50 51 50 55 49 50 49 56 48 49 47 48 64 65 63 64...
result:
ok Everything ok
Test #29:
score: 0
Accepted
time: 875ms
memory: 133480kb
input:
7533
output:
YES 6998 6 7 5 6 4 5 4 8 3 4 2 3 14 15 13 14 12 13 11 12 11 16 10 11 9 10 23 24 22 23 21 22 21 25 20 21 19 20 18 19 17 18 31 32 30 31 29 30 29 33 28 29 28 34 27 28 26 27 41 42 40 41 39 40 38 39 37 38 37 43 36 37 35 36 50 51 49 50 48 49 47 48 47 52 46 47 46 53 45 46 44 45 61 62 60 61 59 60 58 59 57 5...
result:
ok Everything ok
Test #30:
score: 0
Accepted
time: 873ms
memory: 133644kb
input:
5957
output:
YES 5527 6 7 5 6 4 5 4 8 3 4 2 3 14 15 13 14 12 13 11 12 11 16 10 11 9 10 23 24 22 23 21 22 21 25 20 21 19 20 18 19 17 18 31 32 30 31 29 30 29 33 28 29 28 34 27 28 26 27 41 42 40 41 39 40 38 39 37 38 37 43 36 37 35 36 51 52 50 51 49 50 49 53 48 49 47 48 46 47 45 46 44 45 60 61 59 60 58 59 57 58 57 6...
result:
ok Everything ok
Test #31:
score: 0
Accepted
time: 825ms
memory: 134400kb
input:
92651
output:
YES 87225 6 7 5 6 4 5 4 8 3 4 2 3 15 16 14 15 13 14 13 17 12 13 11 12 10 11 9 10 23 24 22 23 21 22 21 25 20 21 20 26 19 20 18 19 33 34 32 33 31 32 30 31 29 30 29 35 28 29 27 28 43 44 42 43 41 42 41 45 40 41 39 40 38 39 37 38 36 37 52 53 51 52 50 51 49 50 49 54 48 49 48 55 47 48 46 47 63 64 62 63 61 ...
result:
ok Everything ok
Test #32:
score: 0
Accepted
time: 844ms
memory: 134124kb
input:
58779
output:
YES 55235 7 8 6 7 5 6 4 5 4 9 3 4 2 3 16 17 15 16 14 15 14 18 13 14 12 13 11 12 10 11 24 25 23 24 22 23 22 26 21 22 21 27 20 21 19 20 34 35 33 34 32 33 31 32 30 31 30 36 29 30 28 29 44 45 43 44 42 43 42 46 41 42 40 41 39 40 38 39 37 38 53 54 52 53 51 52 50 51 50 55 49 50 49 56 48 49 47 48 64 65 63 6...
result:
ok Everything ok
Test #33:
score: 0
Accepted
time: 848ms
memory: 133404kb
input:
12203
output:
YES 11374 6 7 5 6 4 5 4 8 3 4 2 3 15 16 14 15 13 14 13 17 12 13 11 12 10 11 9 10 23 24 22 23 21 22 21 25 20 21 20 26 19 20 18 19 33 34 32 33 31 32 30 31 29 30 29 35 28 29 27 28 43 44 42 43 41 42 41 45 40 41 39 40 38 39 37 38 36 37 52 53 51 52 50 51 49 50 49 54 48 49 48 55 47 48 46 47 63 64 62 63 61 ...
result:
ok Everything ok
Test #34:
score: 0
Accepted
time: 834ms
memory: 134056kb
input:
55627
output:
YES 52258 7 8 6 7 5 6 4 5 4 9 3 4 2 3 16 17 15 16 14 15 14 18 13 14 12 13 11 12 10 11 24 25 23 24 22 23 22 26 21 22 21 27 20 21 19 20 34 35 33 34 32 33 31 32 30 31 30 36 29 30 28 29 44 45 43 44 42 43 42 46 41 42 40 41 39 40 38 39 37 38 53 54 52 53 51 52 50 51 50 55 49 50 49 56 48 49 47 48 64 65 63 6...
result:
ok Everything ok
Test #35:
score: 0
Accepted
time: 854ms
memory: 134332kb
input:
99051
output:
YES 93269 6 7 5 6 4 5 4 8 3 4 2 3 14 15 13 14 12 13 11 12 11 16 10 11 9 10 23 24 22 23 21 22 21 25 20 21 19 20 18 19 17 18 31 32 30 31 29 30 29 33 28 29 28 34 27 28 26 27 41 42 40 41 39 40 38 39 37 38 37 43 36 37 35 36 51 52 50 51 49 50 49 53 48 49 47 48 46 47 45 46 44 45 60 61 59 60 58 59 57 58 57 ...
result:
ok Everything ok
Test #36:
score: 0
Accepted
time: 855ms
memory: 142192kb
input:
811713
output:
YES 770513 7 8 6 7 5 6 4 5 4 9 3 4 2 3 16 17 15 16 14 15 14 18 13 14 12 13 11 12 10 11 24 25 23 24 22 23 22 26 21 22 21 27 20 21 19 20 34 35 33 34 32 33 31 32 30 31 30 36 29 30 28 29 44 45 43 44 42 43 42 46 41 42 40 41 39 40 38 39 37 38 53 54 52 53 51 52 50 51 50 55 49 50 49 56 48 49 47 48 64 65 63 ...
result:
ok Everything ok
Test #37:
score: 0
Accepted
time: 844ms
memory: 137920kb
input:
544133
output:
YES 515717 6 7 5 6 4 5 4 8 3 4 2 3 14 15 13 14 12 13 11 12 11 16 10 11 9 10 23 24 22 23 21 22 21 25 20 21 19 20 18 19 17 18 31 32 30 31 29 30 29 33 28 29 28 34 27 28 26 27 41 42 40 41 39 40 38 39 37 38 37 43 36 37 35 36 51 52 50 51 49 50 49 53 48 49 47 48 46 47 45 46 44 45 60 61 59 60 58 59 57 58 57...
result:
ok Everything ok
Test #38:
score: 0
Accepted
time: 777ms
memory: 135564kb
input:
276553
output:
YES 261516 6 7 5 6 4 5 4 8 3 4 2 3 14 15 13 14 12 13 11 12 11 16 10 11 9 10 23 24 22 23 21 22 21 25 20 21 19 20 18 19 17 18 31 32 30 31 29 30 29 33 28 29 28 34 27 28 26 27 41 42 40 41 39 40 38 39 37 38 37 43 36 37 35 36 51 52 50 51 49 50 49 53 48 49 47 48 46 47 45 46 44 45 60 61 59 60 58 59 57 58 57...
result:
ok Everything ok
Test #39:
score: 0
Accepted
time: 813ms
memory: 142140kb
input:
736904
output:
YES 699266 6 7 5 6 4 5 4 8 3 4 2 3 14 15 13 14 12 13 11 12 11 16 10 11 9 10 23 24 22 23 21 22 21 25 20 21 19 20 18 19 17 18 31 32 30 31 29 30 29 33 28 29 28 34 27 28 26 27 41 42 40 41 39 40 38 39 37 38 37 43 36 37 35 36 51 52 50 51 49 50 49 53 48 49 47 48 46 47 45 46 44 45 60 61 59 60 58 59 57 58 57...
result:
ok Everything ok
Test #40:
score: 0
Accepted
time: 860ms
memory: 142180kb
input:
1000000
output:
YES 949834 7 8 6 7 5 6 4 5 4 9 3 4 2 3 16 17 15 16 14 15 14 18 13 14 12 13 11 12 10 11 24 25 23 24 22 23 22 26 21 22 21 27 20 21 19 20 34 35 33 34 32 33 31 32 30 31 30 36 29 30 28 29 44 45 43 44 42 43 42 46 41 42 40 41 39 40 38 39 37 38 53 54 52 53 51 52 50 51 50 55 49 50 49 56 48 49 47 48 64 65 63 ...
result:
ok Everything ok
Extra Test:
score: 0
Extra Test Passed