QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#323258 | #8215. Isomorphic Delight | karuna | AC ✓ | 67ms | 25652kb | C++20 | 2.4kb | 2024-02-09 01:37:42 | 2024-02-09 01:37:42 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int SZ = 21;
vector<vector<pair<int, int>>> R[SZ + 1]; // rooted trees
vector<vector<pair<int, int>>> T[SZ + 1]; // non-rooted
vector<pair<int, int>> E;
void f(int n, int s, int m, int j, bool h) {
if (s == n) {
if (!h) R[n].push_back(E);
else T[n].push_back(E);
return;
}
assert(n - s >= m);
if (n - s < 2 * m) {
if (m != n - s) j = 0;
m = n - s;
}
if (h && m >= (n + 1) / 2) return;
// don't use m
if (s + m + 1 <= n)
f(n, s, m + 1, 0, h);
// use m
for (int k = j; k < R[m].size(); k++) {
E.push_back({ 1, s + 1 });
for (auto [u, v] : R[m][k]) {
E.push_back({ s + u, s + v });
}
f(n, s + m, m, k + 1, h);
for (int l = 0; l < m; l++) E.pop_back();
}
}
void generate(int n) {
if (n <= 10) f(n, 1, 1, 0, false);
f(n, 1, 1, 0, true);
if (n % 2 == 0) {
for (int i = 0; i < R[n / 2].size(); i++) for (int j = 0; j < i; j++) {
vector<pair<int, int>> E;
E.push_back({ 1, n / 2 + 1 });
for (auto [u, v] : R[n / 2][i]) E.push_back({ u, v });
for (auto [u, v] : R[n / 2][j]) E.push_back({ n / 2 + u, n / 2 + v });
T[n].push_back(E);
}
}
}
int main() {
for (int n = 1; n <= SZ; n++) {
generate(n);
}
int n;
cin >> n;
if (n == 1) {
cout << "YES\n";
cout << 0 << '\n';
}
else if (n <= 5) {
cout << "NO\n";
}
else if (n <= 7) {
cout << "YES\n";
cout << 6 << '\n';
cout << "1 2\n";
cout << "2 3\n";
cout << "3 1\n";
cout << "1 4\n";
cout << "2 5\n";
cout << "5 6\n";
}
else {
int m = 7, p = 0, s = 1;
vector<pair<int, int>> V;
while (s != n) {
while (p == T[m].size()) {
++m;
p = 0;
}
bool f = false;
if (s + m + (p + 1 == T[m].size() ? m + 1 : m) > n) {
f = true;
}
if (s + m == n) f = false;
if (!f) {
//cout << m << ' ';
for (auto [u, v] : T[m][p]) {
V.push_back({ s + u, s + v });
}
++p;
s += m;
}
else {
//cout << n - s << endl;
V.push_back({ s + 1, s + 2 });
V.push_back({ s + 1, s + 3 });
V.push_back({ s + 3, s + 4 });
V.push_back({ s + 1, s + 5 });
for (int i = 6; i <= n - s; i++) {
V.push_back({ s + i - 1, s + i });
}
break;
}
}
cout << "YES\n";
cout << V.size() << '\n';
for (auto [u, v] : V) {
cout << u << ' ' << v << '\n';
}
}
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 8ms
memory: 15516kb
input:
1
output:
YES 0
result:
ok Everything ok
Test #2:
score: 0
Accepted
time: 4ms
memory: 15324kb
input:
6
output:
YES 6 1 2 2 3 3 1 1 4 2 5 5 6
result:
ok Everything ok
Test #3:
score: 0
Accepted
time: 8ms
memory: 15384kb
input:
4
output:
NO
result:
ok Everything ok
Test #4:
score: 0
Accepted
time: 0ms
memory: 15672kb
input:
2
output:
NO
result:
ok Everything ok
Test #5:
score: 0
Accepted
time: 7ms
memory: 15620kb
input:
3
output:
NO
result:
ok Everything ok
Test #6:
score: 0
Accepted
time: 9ms
memory: 15376kb
input:
5
output:
NO
result:
ok Everything ok
Test #7:
score: 0
Accepted
time: 4ms
memory: 15532kb
input:
7
output:
YES 6 1 2 2 3 3 1 1 4 2 5 5 6
result:
ok Everything ok
Test #8:
score: 0
Accepted
time: 3ms
memory: 15580kb
input:
8
output:
YES 6 2 3 2 4 4 5 2 6 6 7 7 8
result:
ok Everything ok
Test #9:
score: 0
Accepted
time: 3ms
memory: 15392kb
input:
9
output:
YES 7 2 3 2 4 4 5 2 6 6 7 7 8 8 9
result:
ok Everything ok
Test #10:
score: 0
Accepted
time: 3ms
memory: 15560kb
input:
10
output:
YES 8 2 3 2 4 4 5 2 6 6 7 7 8 8 9 9 10
result:
ok Everything ok
Test #11:
score: 0
Accepted
time: 8ms
memory: 15528kb
input:
11
output:
YES 9 2 3 2 4 4 5 2 6 6 7 7 8 8 9 9 10 10 11
result:
ok Everything ok
Test #12:
score: 0
Accepted
time: 4ms
memory: 15404kb
input:
12
output:
YES 10 2 3 2 4 4 5 2 6 6 7 7 8 8 9 9 10 10 11 11 12
result:
ok Everything ok
Test #13:
score: 0
Accepted
time: 3ms
memory: 15664kb
input:
13
output:
YES 11 2 3 2 4 4 5 2 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13
result:
ok Everything ok
Test #14:
score: 0
Accepted
time: 0ms
memory: 15388kb
input:
14
output:
YES 12 2 3 2 4 4 5 2 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14
result:
ok Everything ok
Test #15:
score: 0
Accepted
time: 4ms
memory: 15684kb
input:
15
output:
YES 13 2 3 2 4 4 5 2 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15
result:
ok Everything ok
Test #16:
score: 0
Accepted
time: 0ms
memory: 15564kb
input:
16
output:
YES 13 2 3 2 4 4 5 2 6 6 7 7 8 9 13 9 10 9 11 11 12 13 14 14 15 15 16
result:
ok Everything ok
Test #17:
score: 0
Accepted
time: 4ms
memory: 15680kb
input:
17
output:
YES 14 2 3 2 4 4 5 2 6 6 7 7 8 9 10 9 11 11 12 9 13 13 14 14 15 15 16 16 17
result:
ok Everything ok
Test #18:
score: 0
Accepted
time: 3ms
memory: 15508kb
input:
18
output:
YES 15 2 3 2 4 4 5 2 6 6 7 7 8 9 10 9 11 11 12 9 13 13 14 14 15 15 16 16 17 17 18
result:
ok Everything ok
Test #19:
score: 0
Accepted
time: 7ms
memory: 15360kb
input:
19
output:
YES 16 2 3 2 4 4 5 2 6 6 7 7 8 9 10 9 11 11 12 9 13 13 14 14 15 15 16 16 17 17 18 18 19
result:
ok Everything ok
Test #20:
score: 0
Accepted
time: 7ms
memory: 15552kb
input:
598
output:
YES 544 2 3 2 4 4 5 2 6 6 7 7 8 9 13 9 10 9 11 11 12 13 14 14 15 15 16 17 18 18 19 19 20 20 21 17 22 22 23 22 24 24 25 26 27 26 28 28 29 29 30 26 31 31 32 32 33 33 34 35 36 35 37 37 38 38 39 35 40 40 41 40 42 42 43 44 45 45 46 44 47 47 48 48 49 44 50 50 51 51 52 52 53 54 55 55 56 54 57 57 58 58 59 5...
result:
ok Everything ok
Test #21:
score: 0
Accepted
time: 8ms
memory: 15668kb
input:
245
output:
YES 221 2 3 2 4 4 5 2 6 6 7 7 8 9 13 9 10 9 11 11 12 13 14 14 15 15 16 17 18 18 19 19 20 20 21 17 22 22 23 22 24 24 25 26 27 26 28 28 29 29 30 26 31 31 32 32 33 33 34 35 36 35 37 37 38 38 39 35 40 40 41 40 42 42 43 44 45 45 46 44 47 47 48 48 49 44 50 50 51 51 52 52 53 54 55 55 56 54 57 57 58 58 59 5...
result:
ok Everything ok
Test #22:
score: 0
Accepted
time: 2ms
memory: 15580kb
input:
793
output:
YES 724 2 3 2 4 4 5 2 6 6 7 7 8 9 13 9 10 9 11 11 12 13 14 14 15 15 16 17 18 18 19 19 20 20 21 17 22 22 23 22 24 24 25 26 27 26 28 28 29 29 30 26 31 31 32 32 33 33 34 35 36 35 37 37 38 38 39 35 40 40 41 40 42 42 43 44 45 45 46 44 47 47 48 48 49 44 50 50 51 51 52 52 53 54 55 55 56 54 57 57 58 58 59 5...
result:
ok Everything ok
Test #23:
score: 0
Accepted
time: 0ms
memory: 15408kb
input:
133
output:
YES 119 2 3 2 4 4 5 2 6 6 7 7 8 9 13 9 10 9 11 11 12 13 14 14 15 15 16 17 18 18 19 19 20 20 21 17 22 22 23 22 24 24 25 26 27 26 28 28 29 29 30 26 31 31 32 32 33 33 34 35 36 35 37 37 38 38 39 35 40 40 41 40 42 42 43 44 45 45 46 44 47 47 48 48 49 44 50 50 51 51 52 52 53 54 55 55 56 54 57 57 58 58 59 5...
result:
ok Everything ok
Test #24:
score: 0
Accepted
time: 8ms
memory: 15392kb
input:
681
output:
YES 620 2 3 2 4 4 5 2 6 6 7 7 8 9 13 9 10 9 11 11 12 13 14 14 15 15 16 17 18 18 19 19 20 20 21 17 22 22 23 22 24 24 25 26 27 26 28 28 29 29 30 26 31 31 32 32 33 33 34 35 36 35 37 37 38 38 39 35 40 40 41 40 42 42 43 44 45 45 46 44 47 47 48 48 49 44 50 50 51 51 52 52 53 54 55 55 56 54 57 57 58 58 59 5...
result:
ok Everything ok
Test #25:
score: 0
Accepted
time: 4ms
memory: 15568kb
input:
922
output:
YES 843 2 3 2 4 4 5 2 6 6 7 7 8 9 13 9 10 9 11 11 12 13 14 14 15 15 16 17 18 18 19 19 20 20 21 17 22 22 23 22 24 24 25 26 27 26 28 28 29 29 30 26 31 31 32 32 33 33 34 35 36 35 37 37 38 38 39 35 40 40 41 40 42 42 43 44 45 45 46 44 47 47 48 48 49 44 50 50 51 51 52 52 53 54 55 55 56 54 57 57 58 58 59 5...
result:
ok Everything ok
Test #26:
score: 0
Accepted
time: 4ms
memory: 15416kb
input:
876
output:
YES 800 2 3 2 4 4 5 2 6 6 7 7 8 9 13 9 10 9 11 11 12 13 14 14 15 15 16 17 18 18 19 19 20 20 21 17 22 22 23 22 24 24 25 26 27 26 28 28 29 29 30 26 31 31 32 32 33 33 34 35 36 35 37 37 38 38 39 35 40 40 41 40 42 42 43 44 45 45 46 44 47 47 48 48 49 44 50 50 51 51 52 52 53 54 55 55 56 54 57 57 58 58 59 5...
result:
ok Everything ok
Test #27:
score: 0
Accepted
time: 8ms
memory: 15768kb
input:
7740
output:
YES 7191 2 3 2 4 4 5 2 6 6 7 7 8 9 13 9 10 9 11 11 12 13 14 14 15 15 16 17 18 18 19 19 20 20 21 17 22 22 23 22 24 24 25 26 27 26 28 28 29 29 30 26 31 31 32 32 33 33 34 35 36 35 37 37 38 38 39 35 40 40 41 40 42 42 43 44 45 45 46 44 47 47 48 48 49 44 50 50 51 51 52 52 53 54 55 55 56 54 57 57 58 58 59 ...
result:
ok Everything ok
Test #28:
score: 0
Accepted
time: 7ms
memory: 15536kb
input:
2460
output:
YES 2268 2 3 2 4 4 5 2 6 6 7 7 8 9 13 9 10 9 11 11 12 13 14 14 15 15 16 17 18 18 19 19 20 20 21 17 22 22 23 22 24 24 25 26 27 26 28 28 29 29 30 26 31 31 32 32 33 33 34 35 36 35 37 37 38 38 39 35 40 40 41 40 42 42 43 44 45 45 46 44 47 47 48 48 49 44 50 50 51 51 52 52 53 54 55 55 56 54 57 57 58 58 59 ...
result:
ok Everything ok
Test #29:
score: 0
Accepted
time: 3ms
memory: 15748kb
input:
7533
output:
YES 6998 2 3 2 4 4 5 2 6 6 7 7 8 9 13 9 10 9 11 11 12 13 14 14 15 15 16 17 18 18 19 19 20 20 21 17 22 22 23 22 24 24 25 26 27 26 28 28 29 29 30 26 31 31 32 32 33 33 34 35 36 35 37 37 38 38 39 35 40 40 41 40 42 42 43 44 45 45 46 44 47 47 48 48 49 44 50 50 51 51 52 52 53 54 55 55 56 54 57 57 58 58 59 ...
result:
ok Everything ok
Test #30:
score: 0
Accepted
time: 5ms
memory: 15604kb
input:
5957
output:
YES 5527 2 3 2 4 4 5 2 6 6 7 7 8 9 13 9 10 9 11 11 12 13 14 14 15 15 16 17 18 18 19 19 20 20 21 17 22 22 23 22 24 24 25 26 27 26 28 28 29 29 30 26 31 31 32 32 33 33 34 35 36 35 37 37 38 38 39 35 40 40 41 40 42 42 43 44 45 45 46 44 47 47 48 48 49 44 50 50 51 51 52 52 53 54 55 55 56 54 57 57 58 58 59 ...
result:
ok Everything ok
Test #31:
score: 0
Accepted
time: 11ms
memory: 17188kb
input:
92651
output:
YES 87225 2 3 2 4 4 5 2 6 6 7 7 8 9 13 9 10 9 11 11 12 13 14 14 15 15 16 17 18 18 19 19 20 20 21 17 22 22 23 22 24 24 25 26 27 26 28 28 29 29 30 26 31 31 32 32 33 33 34 35 36 35 37 37 38 38 39 35 40 40 41 40 42 42 43 44 45 45 46 44 47 47 48 48 49 44 50 50 51 51 52 52 53 54 55 55 56 54 57 57 58 58 59...
result:
ok Everything ok
Test #32:
score: 0
Accepted
time: 4ms
memory: 16568kb
input:
58779
output:
YES 55235 2 3 2 4 4 5 2 6 6 7 7 8 9 13 9 10 9 11 11 12 13 14 14 15 15 16 17 18 18 19 19 20 20 21 17 22 22 23 22 24 24 25 26 27 26 28 28 29 29 30 26 31 31 32 32 33 33 34 35 36 35 37 37 38 38 39 35 40 40 41 40 42 42 43 44 45 45 46 44 47 47 48 48 49 44 50 50 51 51 52 52 53 54 55 55 56 54 57 57 58 58 59...
result:
ok Everything ok
Test #33:
score: 0
Accepted
time: 4ms
memory: 15636kb
input:
12203
output:
YES 11374 2 3 2 4 4 5 2 6 6 7 7 8 9 13 9 10 9 11 11 12 13 14 14 15 15 16 17 18 18 19 19 20 20 21 17 22 22 23 22 24 24 25 26 27 26 28 28 29 29 30 26 31 31 32 32 33 33 34 35 36 35 37 37 38 38 39 35 40 40 41 40 42 42 43 44 45 45 46 44 47 47 48 48 49 44 50 50 51 51 52 52 53 54 55 55 56 54 57 57 58 58 59...
result:
ok Everything ok
Test #34:
score: 0
Accepted
time: 8ms
memory: 16480kb
input:
55627
output:
YES 52258 2 3 2 4 4 5 2 6 6 7 7 8 9 13 9 10 9 11 11 12 13 14 14 15 15 16 17 18 18 19 19 20 20 21 17 22 22 23 22 24 24 25 26 27 26 28 28 29 29 30 26 31 31 32 32 33 33 34 35 36 35 37 37 38 38 39 35 40 40 41 40 42 42 43 44 45 45 46 44 47 47 48 48 49 44 50 50 51 51 52 52 53 54 55 55 56 54 57 57 58 58 59...
result:
ok Everything ok
Test #35:
score: 0
Accepted
time: 15ms
memory: 17364kb
input:
99051
output:
YES 93269 2 3 2 4 4 5 2 6 6 7 7 8 9 13 9 10 9 11 11 12 13 14 14 15 15 16 17 18 18 19 19 20 20 21 17 22 22 23 22 24 24 25 26 27 26 28 28 29 29 30 26 31 31 32 32 33 33 34 35 36 35 37 37 38 38 39 35 40 40 41 40 42 42 43 44 45 45 46 44 47 47 48 48 49 44 50 50 51 51 52 52 53 54 55 55 56 54 57 57 58 58 59...
result:
ok Everything ok
Test #36:
score: 0
Accepted
time: 60ms
memory: 25412kb
input:
811713
output:
YES 770513 2 3 2 4 4 5 2 6 6 7 7 8 9 13 9 10 9 11 11 12 13 14 14 15 15 16 17 18 18 19 19 20 20 21 17 22 22 23 22 24 24 25 26 27 26 28 28 29 29 30 26 31 31 32 32 33 33 34 35 36 35 37 37 38 38 39 35 40 40 41 40 42 42 43 44 45 45 46 44 47 47 48 48 49 44 50 50 51 51 52 52 53 54 55 55 56 54 57 57 58 58 5...
result:
ok Everything ok
Test #37:
score: 0
Accepted
time: 38ms
memory: 22524kb
input:
544133
output:
YES 515717 2 3 2 4 4 5 2 6 6 7 7 8 9 13 9 10 9 11 11 12 13 14 14 15 15 16 17 18 18 19 19 20 20 21 17 22 22 23 22 24 24 25 26 27 26 28 28 29 29 30 26 31 31 32 32 33 33 34 35 36 35 37 37 38 38 39 35 40 40 41 40 42 42 43 44 45 45 46 44 47 47 48 48 49 44 50 50 51 51 52 52 53 54 55 55 56 54 57 57 58 58 5...
result:
ok Everything ok
Test #38:
score: 0
Accepted
time: 28ms
memory: 18636kb
input:
276553
output:
YES 261516 2 3 2 4 4 5 2 6 6 7 7 8 9 13 9 10 9 11 11 12 13 14 14 15 15 16 17 18 18 19 19 20 20 21 17 22 22 23 22 24 24 25 26 27 26 28 28 29 29 30 26 31 31 32 32 33 33 34 35 36 35 37 37 38 38 39 35 40 40 41 40 42 42 43 44 45 45 46 44 47 47 48 48 49 44 50 50 51 51 52 52 53 54 55 55 56 54 57 57 58 58 5...
result:
ok Everything ok
Test #39:
score: 0
Accepted
time: 65ms
memory: 24736kb
input:
736904
output:
YES 699266 2 3 2 4 4 5 2 6 6 7 7 8 9 13 9 10 9 11 11 12 13 14 14 15 15 16 17 18 18 19 19 20 20 21 17 22 22 23 22 24 24 25 26 27 26 28 28 29 29 30 26 31 31 32 32 33 33 34 35 36 35 37 37 38 38 39 35 40 40 41 40 42 42 43 44 45 45 46 44 47 47 48 48 49 44 50 50 51 51 52 52 53 54 55 55 56 54 57 57 58 58 5...
result:
ok Everything ok
Test #40:
score: 0
Accepted
time: 67ms
memory: 25652kb
input:
1000000
output:
YES 949834 2 3 2 4 4 5 2 6 6 7 7 8 9 13 9 10 9 11 11 12 13 14 14 15 15 16 17 18 18 19 19 20 20 21 17 22 22 23 22 24 24 25 26 27 26 28 28 29 29 30 26 31 31 32 32 33 33 34 35 36 35 37 37 38 38 39 35 40 40 41 40 42 42 43 44 45 45 46 44 47 47 48 48 49 44 50 50 51 51 52 52 53 54 55 55 56 54 57 57 58 58 5...
result:
ok Everything ok
Extra Test:
score: 0
Extra Test Passed