QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#369094 | #8215. Isomorphic Delight | .5 ulp (Maxim Plyushkin, Egor Belousov, Maxim Inyutin)# | AC ✓ | 1476ms | 221800kb | C++20 | 2.6kb | 2024-03-27 20:30:43 | 2024-03-27 20:30:44 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 100;
uint64_t splitmix(uint64_t x) {
x += 0x9e3779b97f4a7c15;
(x ^= x >> 30) *= 0xbf58476d1ce4e5b9;
(x ^= x >> 27) *= 0x94d049bb133111eb;
return x ^ x >> 31;
}
int n;
vector<int> nei[N];
int sz[N];
vector<int> cent;
void findcent(int v, int p) {
bool cent = 1;
sz[v] = 1;
for (auto u: nei[v]) if (u != p) {
findcent(u, v);
sz[v] += sz[u];
cent &= sz[u] * 2 <= n;
}
if (cent && sz[v] * 2 >= n) ::cent.push_back(v);
}
uint64_t h[N];
bool ok;
uint64_t treehash(int v, int p) {
if (!ok) return 0;
uint64_t x = 0;
for (auto u: nei[v]) if (u != p) x += treehash(u, v);
for (auto u: nei[v]) if (u != p && ok)
for (auto w: nei[v]) if (w != p) if (w == u) break; else ok &= h[w] != h[u];
return h[v] = splitmix(x);
}
vector<vector<int>> rooted[N];
vector<vector<int>> unrooted[N];
set<uint64_t> urs;
void build(vector<int> p, int n, int m, int i, auto f) {
if (!n) f(p);
if (m > n) return;
while (++i < rooted[m].size()) {
auto t = rooted[m][i];
for (auto& x: t) x += p.size() + 1;
t.insert(t.begin(), 0);
t.insert(t.begin(), p.begin(), p.end());
build(t, n - m, m, i, f);
}
build(p, n, m + 1, -1, f);
}
constexpr int W = 1e6 + 1;
int can[W], last[W];
int main() {
cin.tie(0)->sync_with_stdio(0);
rooted[1] = {{}};
unrooted[1] = {{}};
int nr = 1, nu = 1, su = 1;
for (n = 2; nr < 1000000; nr += rooted[n].size(), nu += unrooted[n].size(), su += unrooted[n].size() * n, ++n)
build({}, n - 1, 0, -1, [&](auto p) {
for (int i = 0; i < n; ++i) nei[i].clear();
for (int i = 1; i < n; ++i) nei[i].push_back(p[i - 1]), nei[p[i - 1]].push_back(i);
rooted[n].push_back(p);
ok = 1;
cent.clear();
findcent(0, 0);
uint64_t h = treehash(cent[0], cent.back()), hh = h;
if (ok && (cent.size() == 1 || h != (hh = treehash(cent[1], cent[0]))) && ok && urs.insert(h + hh).second) unrooted[n].push_back(p);
});
for (int w = 0; ++w < 22; )
for (int i = W; i--; ) if (can[i] || !i)
for (int c = 1, ww = i + w; ww < W && c <= unrooted[w].size() && can[ww] < can[i] + c; ++c, ww += w) can[ww] = can[i] + c, last[ww] = w;
int n; cin >> n;
if (n > 1 && n < 6) return cout << "NO", 0;
cout << "YES\n";
if (n == 6) {
cout << "6\n1 2\n2 3\n1 3\n3 4\n2 5\n5 6\n";
return 0;
}
cout << n - can[n] << '\n';
int d = 0;
while (n) {
auto p = unrooted[last[n]].back(); unrooted[last[n]].pop_back();
for (int i = 0; i < p.size(); ++i) cout << d + i + 2 << ' ' << d + p[i] + 1 << '\n';
d += last[n];
n -= last[n];
}
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1387ms
memory: 220148kb
input:
1
output:
YES 0
result:
ok Everything ok
Test #2:
score: 0
Accepted
time: 1374ms
memory: 220152kb
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: 1336ms
memory: 218408kb
input:
4
output:
NO
result:
ok Everything ok
Test #4:
score: 0
Accepted
time: 1358ms
memory: 220008kb
input:
2
output:
NO
result:
ok Everything ok
Test #5:
score: 0
Accepted
time: 1412ms
memory: 221572kb
input:
3
output:
NO
result:
ok Everything ok
Test #6:
score: 0
Accepted
time: 1476ms
memory: 218448kb
input:
5
output:
NO
result:
ok Everything ok
Test #7:
score: 0
Accepted
time: 1391ms
memory: 219400kb
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: 1371ms
memory: 221212kb
input:
8
output:
YES 6 2 1 3 1 4 3 5 1 6 5 7 6
result:
ok Everything ok
Test #9:
score: 0
Accepted
time: 1382ms
memory: 217316kb
input:
9
output:
YES 7 2 1 3 1 4 3 5 1 6 5 7 6 8 7
result:
ok Everything ok
Test #10:
score: 0
Accepted
time: 1423ms
memory: 220520kb
input:
10
output:
YES 8 2 1 3 1 4 3 5 4 6 1 7 6 8 7 9 8
result:
ok Everything ok
Test #11:
score: 0
Accepted
time: 1362ms
memory: 217640kb
input:
11
output:
YES 9 2 1 3 1 4 3 5 4 6 5 7 3 8 7 9 8 10 9
result:
ok Everything ok
Test #12:
score: 0
Accepted
time: 1381ms
memory: 217104kb
input:
12
output:
YES 10 2 1 3 1 4 3 5 4 6 5 7 3 8 7 9 8 10 9 11 10
result:
ok Everything ok
Test #13:
score: 0
Accepted
time: 1347ms
memory: 221232kb
input:
13
output:
YES 11 2 1 3 1 4 3 5 4 6 5 7 6 8 3 9 8 10 9 11 10 12 11
result:
ok Everything ok
Test #14:
score: 0
Accepted
time: 1379ms
memory: 218496kb
input:
14
output:
YES 12 2 1 3 1 4 3 5 4 6 5 7 6 8 7 9 4 10 9 11 10 12 11 13 12
result:
ok Everything ok
Test #15:
score: 0
Accepted
time: 1332ms
memory: 217608kb
input:
15
output:
YES 13 2 1 3 1 4 3 5 1 6 5 7 6 8 7 10 9 11 9 12 11 13 9 14 13 15 14
result:
ok Everything ok
Test #16:
score: 0
Accepted
time: 1396ms
memory: 217132kb
input:
16
output:
YES 13 2 1 3 1 4 3 5 1 6 5 7 6 8 7 10 9 11 9 12 11 13 9 14 13 15 14
result:
ok Everything ok
Test #17:
score: 0
Accepted
time: 1344ms
memory: 219080kb
input:
17
output:
YES 14 2 1 3 1 4 3 5 4 6 1 7 6 8 7 9 8 11 10 12 10 13 12 14 10 15 14 16 15
result:
ok Everything ok
Test #18:
score: 0
Accepted
time: 1393ms
memory: 220616kb
input:
18
output:
YES 15 2 1 3 1 4 3 5 4 6 1 7 6 8 7 9 8 11 10 12 10 13 12 14 10 15 14 16 15 17 16
result:
ok Everything ok
Test #19:
score: 0
Accepted
time: 1388ms
memory: 218396kb
input:
19
output:
YES 16 2 1 3 1 4 3 5 4 6 1 7 6 8 7 9 8 11 10 12 10 13 12 14 10 15 14 16 15 17 16 18 17
result:
ok Everything ok
Test #20:
score: 0
Accepted
time: 1362ms
memory: 220252kb
input:
598
output:
YES 544 2 1 3 1 4 3 5 4 6 5 7 6 8 3 9 8 10 9 11 10 12 11 14 13 15 13 16 15 17 16 18 17 19 15 20 19 21 20 22 21 23 22 24 23 26 25 27 25 28 27 29 28 30 29 31 25 32 31 33 32 34 33 35 34 36 35 38 37 39 37 40 39 41 40 42 41 43 37 44 43 45 44 46 43 47 46 48 47 50 49 51 49 52 51 53 52 54 49 55 54 56 55 57 ...
result:
ok Everything ok
Test #21:
score: 0
Accepted
time: 1382ms
memory: 219456kb
input:
245
output:
YES 221 2 1 3 1 4 3 5 4 6 5 7 3 8 7 9 8 10 9 11 10 13 12 14 12 15 14 16 15 17 16 18 12 19 18 20 19 21 20 22 21 24 23 25 23 26 25 27 26 28 23 29 28 30 29 31 30 32 31 33 32 35 34 36 34 37 36 38 37 39 34 40 39 41 40 42 39 43 42 44 43 46 45 47 45 48 47 49 48 50 45 51 50 52 50 53 52 54 53 55 54 57 56 58 ...
result:
ok Everything ok
Test #22:
score: 0
Accepted
time: 1333ms
memory: 217272kb
input:
793
output:
YES 724 2 1 3 1 4 3 5 4 6 5 7 6 8 7 9 4 10 9 11 10 12 11 13 12 15 14 16 14 17 16 18 17 19 18 20 19 21 16 22 21 23 22 24 23 25 24 26 25 28 27 29 27 30 29 31 30 32 31 33 29 34 33 35 34 36 35 37 36 38 37 39 38 41 40 42 40 43 42 44 43 45 44 46 42 47 46 48 47 49 46 50 49 51 50 52 51 54 53 55 53 56 55 57 ...
result:
ok Everything ok
Test #23:
score: 0
Accepted
time: 1376ms
memory: 217136kb
input:
133
output:
YES 119 2 1 3 1 4 3 5 4 6 5 7 3 8 7 9 8 10 9 11 10 13 12 14 12 15 14 16 15 17 16 18 12 19 18 20 19 21 20 22 21 24 23 25 23 26 25 27 26 28 23 29 28 30 29 31 30 32 31 33 32 35 34 36 34 37 36 38 37 39 34 40 39 41 40 42 39 43 42 44 43 46 45 47 45 48 47 49 48 50 45 51 50 52 50 53 52 54 53 55 54 57 56 58 ...
result:
ok Everything ok
Test #24:
score: 0
Accepted
time: 1458ms
memory: 218480kb
input:
681
output:
YES 620 2 1 3 1 4 3 5 4 6 5 7 6 8 7 9 4 10 9 11 10 12 11 13 12 15 14 16 14 17 16 18 17 19 18 20 19 21 16 22 21 23 22 24 23 25 24 26 25 28 27 29 27 30 29 31 30 32 31 33 29 34 33 35 34 36 35 37 36 38 37 39 38 41 40 42 40 43 42 44 43 45 44 46 42 47 46 48 47 49 46 50 49 51 50 52 51 54 53 55 53 56 55 57 ...
result:
ok Everything ok
Test #25:
score: 0
Accepted
time: 1357ms
memory: 218524kb
input:
922
output:
YES 843 2 1 3 1 4 3 5 4 6 5 7 6 8 7 9 4 10 9 11 10 12 11 13 12 15 14 16 14 17 16 18 17 19 18 20 19 21 16 22 21 23 22 24 23 25 24 26 25 28 27 29 27 30 29 31 30 32 31 33 29 34 33 35 34 36 35 37 36 38 37 39 38 41 40 42 40 43 42 44 43 45 44 46 42 47 46 48 47 49 46 50 49 51 50 52 51 54 53 55 53 56 55 57 ...
result:
ok Everything ok
Test #26:
score: 0
Accepted
time: 1355ms
memory: 218100kb
input:
876
output:
YES 800 2 1 3 1 4 3 5 4 6 5 7 6 8 7 9 4 10 9 11 10 12 11 13 12 15 14 16 14 17 16 18 17 19 18 20 19 21 16 22 21 23 22 24 23 25 24 26 25 28 27 29 27 30 29 31 30 32 31 33 29 34 33 35 34 36 35 37 36 38 37 39 38 41 40 42 40 43 42 44 43 45 44 46 42 47 46 48 47 49 46 50 49 51 50 52 51 54 53 55 53 56 55 57 ...
result:
ok Everything ok
Test #27:
score: 0
Accepted
time: 1367ms
memory: 221800kb
input:
7740
output:
YES 7191 2 1 3 1 4 3 5 4 6 5 7 6 8 7 9 8 10 4 11 10 12 11 13 12 14 13 15 14 17 16 18 16 19 18 20 19 21 20 22 21 23 22 24 19 25 24 26 25 27 26 28 27 29 28 30 29 32 31 33 31 34 33 35 34 36 35 37 36 38 37 39 33 40 39 41 40 42 41 43 42 44 43 45 44 47 46 48 46 49 48 50 49 51 50 52 51 53 48 54 53 55 54 56...
result:
ok Everything ok
Test #28:
score: 0
Accepted
time: 1383ms
memory: 220240kb
input:
2460
output:
YES 2268 2 1 3 1 4 3 5 4 6 5 7 6 8 7 9 4 10 9 11 10 12 11 13 12 14 13 16 15 17 15 18 17 19 18 20 19 21 20 22 21 23 17 24 23 25 24 26 25 27 26 28 27 30 29 31 29 32 31 33 32 34 33 35 34 36 31 37 36 38 37 39 38 40 39 41 40 42 41 44 43 45 43 46 45 47 46 48 47 49 45 50 49 51 50 52 51 53 52 54 53 55 54 56...
result:
ok Everything ok
Test #29:
score: 0
Accepted
time: 1367ms
memory: 220284kb
input:
7533
output:
YES 6998 2 1 3 1 4 3 5 4 6 5 7 6 8 7 9 8 10 4 11 10 12 11 13 12 14 13 15 14 17 16 18 16 19 18 20 19 21 20 22 21 23 22 24 19 25 24 26 25 27 26 28 27 29 28 30 29 32 31 33 31 34 33 35 34 36 35 37 36 38 37 39 33 40 39 41 40 42 41 43 42 44 43 45 44 47 46 48 46 49 48 50 49 51 50 52 51 53 48 54 53 55 54 56...
result:
ok Everything ok
Test #30:
score: 0
Accepted
time: 1388ms
memory: 217608kb
input:
5957
output:
YES 5527 2 1 3 1 4 3 5 4 6 5 7 6 8 7 9 8 10 4 11 10 12 11 13 12 14 13 15 14 17 16 18 16 19 18 20 19 21 20 22 21 23 22 24 19 25 24 26 25 27 26 28 27 29 28 30 29 32 31 33 31 34 33 35 34 36 35 37 36 38 37 39 33 40 39 41 40 42 41 43 42 44 43 45 44 47 46 48 46 49 48 50 49 51 50 52 51 53 48 54 53 55 54 56...
result:
ok Everything ok
Test #31:
score: 0
Accepted
time: 1396ms
memory: 219256kb
input:
92651
output:
YES 87225 2 1 3 1 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 10 12 5 13 12 14 13 15 14 16 15 17 16 18 17 20 19 21 19 22 21 23 22 24 23 25 24 26 25 27 26 28 27 29 23 30 29 31 30 32 31 33 32 34 33 35 34 36 35 38 37 39 37 40 39 41 40 42 41 43 42 44 43 45 44 46 45 47 40 48 47 49 48 50 49 51 50 52 51 53 52 54 53 56...
result:
ok Everything ok
Test #32:
score: 0
Accepted
time: 1346ms
memory: 219984kb
input:
58779
output:
YES 55235 2 1 3 1 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 10 12 5 13 12 14 13 15 14 16 15 17 16 18 17 20 19 21 19 22 21 23 22 24 23 25 24 26 25 27 26 28 27 29 23 30 29 31 30 32 31 33 32 34 33 35 34 36 35 38 37 39 37 40 39 41 40 42 41 43 42 44 43 45 44 46 45 47 40 48 47 49 48 50 49 51 50 52 51 53 52 54 53 56...
result:
ok Everything ok
Test #33:
score: 0
Accepted
time: 1382ms
memory: 218748kb
input:
12203
output:
YES 11374 2 1 3 1 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 5 12 11 13 12 14 13 15 14 16 15 18 17 19 17 20 19 21 20 22 21 23 22 24 23 25 24 26 20 27 26 28 27 29 28 30 29 31 30 32 31 34 33 35 33 36 35 37 36 38 37 39 38 40 39 41 36 42 41 43 42 44 43 45 44 46 45 47 46 48 47 50 49 51 49 52 51 53 52 54 53 55 54 56...
result:
ok Everything ok
Test #34:
score: 0
Accepted
time: 1424ms
memory: 217348kb
input:
55627
output:
YES 52258 2 1 3 1 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 10 12 5 13 12 14 13 15 14 16 15 17 16 18 17 20 19 21 19 22 21 23 22 24 23 25 24 26 25 27 26 28 27 29 23 30 29 31 30 32 31 33 32 34 33 35 34 36 35 38 37 39 37 40 39 41 40 42 41 43 42 44 43 45 44 46 45 47 40 48 47 49 48 50 49 51 50 52 51 53 52 54 53 56...
result:
ok Everything ok
Test #35:
score: 0
Accepted
time: 1417ms
memory: 216936kb
input:
99051
output:
YES 93269 2 1 3 1 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 10 12 5 13 12 14 13 15 14 16 15 17 16 18 17 20 19 21 19 22 21 23 22 24 23 25 24 26 25 27 26 28 27 29 23 30 29 31 30 32 31 33 32 34 33 35 34 36 35 38 37 39 37 40 39 41 40 42 41 43 42 44 43 45 44 46 45 47 40 48 47 49 48 50 49 51 50 52 51 53 52 54 53 56...
result:
ok Everything ok
Test #36:
score: 0
Accepted
time: 1441ms
memory: 218304kb
input:
811713
output:
YES 770513 2 1 3 1 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 10 12 11 13 12 14 6 15 14 16 15 17 16 18 17 19 18 20 19 21 20 23 22 24 22 25 24 26 25 27 26 28 27 29 28 30 29 31 30 32 31 33 32 34 27 35 34 36 35 37 36 38 37 39 38 40 39 41 40 42 41 44 43 45 43 46 45 47 46 48 47 49 48 50 49 51 50 52 51 53 52 54 53 5...
result:
ok Everything ok
Test #37:
score: 0
Accepted
time: 1432ms
memory: 220516kb
input:
544133
output:
YES 515717 2 1 3 1 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 10 12 11 13 6 14 13 15 14 16 15 17 16 18 17 19 18 20 19 22 21 23 21 24 23 25 24 26 25 27 26 28 27 29 28 30 29 31 30 32 31 33 25 34 33 35 34 36 35 37 36 38 37 39 38 40 39 42 41 43 41 44 43 45 44 46 45 47 46 48 47 49 48 50 49 51 50 52 45 53 52 54 53 5...
result:
ok Everything ok
Test #38:
score: 0
Accepted
time: 1366ms
memory: 217364kb
input:
276553
output:
YES 261516 2 1 3 1 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 10 12 11 13 6 14 13 15 14 16 15 17 16 18 17 19 18 20 19 22 21 23 21 24 23 25 24 26 25 27 26 28 27 29 28 30 29 31 30 32 31 33 25 34 33 35 34 36 35 37 36 38 37 39 38 40 39 42 41 43 41 44 43 45 44 46 45 47 46 48 47 49 48 50 49 51 50 52 45 53 52 54 53 5...
result:
ok Everything ok
Test #39:
score: 0
Accepted
time: 1428ms
memory: 220896kb
input:
736904
output:
YES 699266 2 1 3 1 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 10 12 11 13 12 14 6 15 14 16 15 17 16 18 17 19 18 20 19 21 20 23 22 24 22 25 24 26 25 27 26 28 27 29 28 30 29 31 30 32 31 33 32 34 27 35 34 36 35 37 36 38 37 39 38 40 39 41 40 42 41 44 43 45 43 46 45 47 46 48 47 49 48 50 49 51 50 52 51 53 52 54 53 5...
result:
ok Everything ok
Test #40:
score: 0
Accepted
time: 1437ms
memory: 220164kb
input:
1000000
output:
YES 949834 2 1 3 1 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 10 12 11 13 12 14 6 15 14 16 15 17 16 18 17 19 18 20 19 21 20 23 22 24 22 25 24 26 25 27 26 28 27 29 28 30 29 31 30 32 31 33 32 34 27 35 34 36 35 37 36 38 37 39 38 40 39 41 40 42 41 44 43 45 43 46 45 47 46 48 47 49 48 50 49 51 50 52 51 53 52 54 53 5...
result:
ok Everything ok
Extra Test:
score: 0
Extra Test Passed