QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#548463 | #8215. Isomorphic Delight | HuTao | AC ✓ | 407ms | 183676kb | C++14 | 3.3kb | 2024-09-05 18:42:17 | 2024-09-05 18:42:17 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5, K = 23;
int n, m = 21;
vector<string> t1[K], t0[K];
int f[K][N], pre[K][N];
int q[N], hh, tt;
int pid;
vector<pair<int, int> > e;
inline bool CornerCases(int n)
{
if(n == 1) return puts("YES\n0"), 1;
if(n <= 5) return puts("NO"), 1;
if(n == 6)
{
puts("YES");
puts("6");
puts("1 2");
puts("1 3");
puts("2 3");
puts("1 4");
puts("4 5");
puts("2 6");
return 1;
}
return 0;
}
inline void DFS(int n, string now, int siz, int lim, int pos, vector<string> &t)
{
if((int)now.size() > n * 2) return ;
if((int)now.size() == n * 2)
{
t.push_back("(" + now + ")");
return ;
}
if(siz > lim) return ;
DFS(n, now, siz + 1, lim, 0, t);
for(int i = pos; i < (int)t1[siz].size(); i ++ )
DFS(n, now + t1[siz][i], siz, lim, i + 1, t);
}
inline void SearchRootedTrees(int k)
{
t1[1].push_back("()");
for(int i = 2; i <= k; i ++ ) DFS(i - 1, "", 1, i - 1, 0, t1[i]);
}
inline void SearchUnrootedTrees(int k)
{
t0[1].push_back("()");
for(int i = 2; i <= k; i ++ )
{
DFS(i - 1, "", 1, (i - 1) / 2, 0, t0[i]);
if(~i & 1)
{
for(int j = 0; j < (int)t1[i / 2].size(); j ++ )
for(int k = j + 1; k < (int)t1[i / 2].size(); k ++ )
{
t0[i].push_back(t1[i / 2][j]);
t0[i].back().pop_back();
t0[i].back() += t1[i / 2][k] + ")";
}
}
}
// for(int i = 1; i <= 8; i ++ )
// {
// printf("#%d\n", i);
// for(string t : t0[i]) puts(t.c_str());
// }
}
inline void DP(int n)
{
memset(f[1], -0x3f, sizeof f[1]);
f[1][0] = 0, f[1][1] = 1;
for(int i = 2; i <= m; i ++ )
{
int c = t0[i].size();
for(int j = 0; j < i; j ++ )
{
f[i][j] = f[i - 1][j], pre[i][j] = j;
hh = tt = 0, q[0] = 0;
for(int k = 1; k <= (n - j) / i; k ++ )
{
while(hh <= tt && q[hh] < k - c) hh ++ ;
while(hh <= tt && f[i - 1][q[tt] * i + j] - q[tt] <= f[i - 1][k * i + j] - k) tt -- ;
q[ ++ tt] = k;
f[i][k * i + j] = f[i - 1][q[hh] * i + j] + k - q[hh];
pre[i][k * i + j] = q[hh] * i + j;
}
}
}
}
inline int GetTree(string &str, int l, int r)
{
int u = ++ pid;
for(int j = l + 1, k; j < r; j = k)
{
k = j + 1;
int s = 1;
while(s)
{
s += str[k] == '(' ? 1 : -1;
k ++ ;
}
e.emplace_back(u, GetTree(str, j, k - 1));
}
return u;
}
int main()
{
scanf("%d", &n);
if(CornerCases(n)) return 0;
SearchRootedTrees(m / 2);
SearchUnrootedTrees(m);
DP(n);
for(int i = m, j = n; i >= 1; i -- )
{
int c = (j - pre[i][j]) / i;
for(int k = 0; k < c; k ++ ) GetTree(t0[i][k], 0, i * 2 - 1);
j = pre[i][j];
}
puts("YES");
printf("%d\n", (int)e.size());
for(pair<int, int> i : e) printf("%d %d\n", i.first, i.second);
return 0;
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3708kb
input:
1
output:
YES 0
result:
ok Everything ok
Test #2:
score: 0
Accepted
time: 0ms
memory: 3664kb
input:
6
output:
YES 6 1 2 1 3 2 3 1 4 4 5 2 6
result:
ok Everything ok
Test #3:
score: 0
Accepted
time: 0ms
memory: 3664kb
input:
4
output:
NO
result:
ok Everything ok
Test #4:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
2
output:
NO
result:
ok Everything ok
Test #5:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
3
output:
NO
result:
ok Everything ok
Test #6:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
5
output:
NO
result:
ok Everything ok
Test #7:
score: 0
Accepted
time: 213ms
memory: 97420kb
input:
7
output:
YES 6 1 2 3 4 1 3 6 7 5 6 1 5
result:
ok Everything ok
Test #8:
score: 0
Accepted
time: 213ms
memory: 80840kb
input:
8
output:
YES 6 1 2 3 4 1 3 6 7 5 6 1 5
result:
ok Everything ok
Test #9:
score: 0
Accepted
time: 216ms
memory: 72624kb
input:
9
output:
YES 7 3 4 2 3 1 2 5 6 7 8 5 7 1 5
result:
ok Everything ok
Test #10:
score: 0
Accepted
time: 222ms
memory: 97248kb
input:
10
output:
YES 8 4 5 3 4 2 3 1 2 6 7 8 9 6 8 1 6
result:
ok Everything ok
Test #11:
score: 0
Accepted
time: 216ms
memory: 97220kb
input:
11
output:
YES 9 2 3 1 2 5 6 4 5 1 4 9 10 8 9 7 8 1 7
result:
ok Everything ok
Test #12:
score: 0
Accepted
time: 216ms
memory: 97244kb
input:
12
output:
YES 10 5 6 4 5 3 4 2 3 1 2 8 9 10 11 8 10 7 8 1 7
result:
ok Everything ok
Test #13:
score: 0
Accepted
time: 219ms
memory: 97152kb
input:
13
output:
YES 11 3 4 2 3 1 2 7 8 6 7 5 6 1 5 9 10 11 12 9 11 1 9
result:
ok Everything ok
Test #14:
score: 0
Accepted
time: 218ms
memory: 97368kb
input:
14
output:
YES 12 6 7 5 6 4 5 3 4 2 3 1 2 10 11 12 13 10 12 9 10 8 9 1 8
result:
ok Everything ok
Test #15:
score: 0
Accepted
time: 212ms
memory: 97160kb
input:
15
output:
YES 13 3 4 2 3 1 2 5 6 7 8 5 7 1 5 9 10 11 12 9 11 14 15 13 14 9 13
result:
ok Everything ok
Test #16:
score: 0
Accepted
time: 220ms
memory: 97196kb
input:
16
output:
YES 13 3 4 2 3 1 2 5 6 7 8 5 7 1 5 9 10 11 12 9 11 14 15 13 14 9 13
result:
ok Everything ok
Test #17:
score: 0
Accepted
time: 217ms
memory: 97204kb
input:
17
output:
YES 14 4 5 3 4 2 3 1 2 6 7 8 9 6 8 1 6 10 11 12 13 10 12 15 16 14 15 10 14
result:
ok Everything ok
Test #18:
score: 0
Accepted
time: 214ms
memory: 97164kb
input:
18
output:
YES 15 4 5 3 4 2 3 1 2 6 7 8 9 6 8 1 6 12 13 11 12 10 11 14 15 16 17 14 16 10 14
result:
ok Everything ok
Test #19:
score: 0
Accepted
time: 216ms
memory: 97180kb
input:
19
output:
YES 16 4 5 3 4 2 3 1 2 6 7 8 9 6 8 1 6 10 11 13 14 12 13 10 12 17 18 16 17 15 16 10 15
result:
ok Everything ok
Test #20:
score: 0
Accepted
time: 224ms
memory: 97280kb
input:
598
output:
YES 544 3 4 2 3 1 2 7 8 6 7 5 6 1 5 9 10 11 12 9 11 1 9 14 15 13 14 18 19 17 18 16 17 13 16 23 24 22 23 21 22 20 21 13 20 26 27 25 26 30 31 29 30 28 29 25 28 33 34 35 36 33 35 32 33 25 32 38 39 37 38 42 43 41 42 40 41 37 40 44 45 47 48 46 47 44 46 37 44 50 51 49 50 52 53 54 55 52 54 49 52 59 60 58 5...
result:
ok Everything ok
Test #21:
score: 0
Accepted
time: 216ms
memory: 97148kb
input:
245
output:
YES 221 5 6 4 5 3 4 2 3 1 2 8 9 10 11 8 10 7 8 1 7 16 17 15 16 14 15 13 14 12 13 18 19 21 22 20 21 18 20 12 18 25 26 27 28 25 27 24 25 23 24 29 30 32 33 31 32 29 31 23 29 35 36 34 35 39 40 38 39 37 38 34 37 41 42 43 44 41 43 34 41 46 47 45 46 49 50 48 49 45 48 54 55 53 54 52 53 51 52 45 51 57 58 56 ...
result:
ok Everything ok
Test #22:
score: 0
Accepted
time: 211ms
memory: 97216kb
input:
793
output:
YES 724 6 7 5 6 4 5 3 4 2 3 1 2 10 11 12 13 10 12 9 10 8 9 1 8 19 20 18 19 17 18 16 17 15 16 14 15 22 23 25 26 24 25 22 24 21 22 14 21 32 33 31 32 30 31 29 30 28 29 27 28 35 36 34 35 38 39 37 38 34 37 27 34 45 46 44 45 43 44 42 43 41 42 40 41 47 48 51 52 50 51 49 50 47 49 40 47 58 59 57 58 56 57 55 ...
result:
ok Everything ok
Test #23:
score: 0
Accepted
time: 212ms
memory: 97244kb
input:
133
output:
YES 119 5 6 4 5 3 4 2 3 1 2 8 9 10 11 8 10 7 8 1 7 16 17 15 16 14 15 13 14 12 13 18 19 21 22 20 21 18 20 12 18 25 26 27 28 25 27 24 25 23 24 29 30 32 33 31 32 29 31 23 29 35 36 34 35 39 40 38 39 37 38 34 37 41 42 43 44 41 43 34 41 46 47 45 46 49 50 48 49 45 48 54 55 53 54 52 53 51 52 45 51 57 58 56 ...
result:
ok Everything ok
Test #24:
score: 0
Accepted
time: 213ms
memory: 97148kb
input:
681
output:
YES 620 6 7 5 6 4 5 3 4 2 3 1 2 10 11 12 13 10 12 9 10 8 9 1 8 19 20 18 19 17 18 16 17 15 16 14 15 22 23 25 26 24 25 22 24 21 22 14 21 32 33 31 32 30 31 29 30 28 29 27 28 35 36 34 35 38 39 37 38 34 37 27 34 45 46 44 45 43 44 42 43 41 42 40 41 47 48 51 52 50 51 49 50 47 49 40 47 58 59 57 58 56 57 55 ...
result:
ok Everything ok
Test #25:
score: 0
Accepted
time: 214ms
memory: 99336kb
input:
922
output:
YES 843 6 7 5 6 4 5 3 4 2 3 1 2 10 11 12 13 10 12 9 10 8 9 1 8 19 20 18 19 17 18 16 17 15 16 14 15 22 23 25 26 24 25 22 24 21 22 14 21 32 33 31 32 30 31 29 30 28 29 27 28 35 36 34 35 38 39 37 38 34 37 27 34 45 46 44 45 43 44 42 43 41 42 40 41 47 48 51 52 50 51 49 50 47 49 40 47 58 59 57 58 56 57 55 ...
result:
ok Everything ok
Test #26:
score: 0
Accepted
time: 216ms
memory: 97360kb
input:
876
output:
YES 800 6 7 5 6 4 5 3 4 2 3 1 2 10 11 12 13 10 12 9 10 8 9 1 8 19 20 18 19 17 18 16 17 15 16 14 15 22 23 25 26 24 25 22 24 21 22 14 21 32 33 31 32 30 31 29 30 28 29 27 28 35 36 34 35 38 39 37 38 34 37 27 34 45 46 44 45 43 44 42 43 41 42 40 41 47 48 51 52 50 51 49 50 47 49 40 47 58 59 57 58 56 57 55 ...
result:
ok Everything ok
Test #27:
score: 0
Accepted
time: 218ms
memory: 99480kb
input:
7740
output:
YES 7191 7 8 6 7 5 6 4 5 3 4 2 3 1 2 12 13 14 15 12 14 11 12 10 11 9 10 1 9 22 23 21 22 20 21 19 20 18 19 17 18 16 17 26 27 29 30 28 29 26 28 25 26 24 25 16 24 37 38 36 37 35 36 34 35 33 34 32 33 31 32 41 42 40 41 44 45 43 44 40 43 39 40 31 39 52 53 51 52 50 51 49 50 48 49 47 48 46 47 55 56 59 60 58...
result:
ok Everything ok
Test #28:
score: 0
Accepted
time: 218ms
memory: 97208kb
input:
2460
output:
YES 2268 4 5 3 4 2 3 1 2 6 7 8 9 6 8 1 6 13 14 12 13 11 12 10 11 1 10 18 19 17 18 16 17 15 16 20 21 22 23 20 22 15 20 25 26 27 28 25 27 24 25 15 24 32 33 31 32 30 31 29 30 34 35 36 37 34 36 29 34 38 39 41 42 40 41 38 40 29 38 45 46 44 45 43 44 50 51 49 50 48 49 47 48 43 47 53 54 55 56 53 55 52 53 43...
result:
ok Everything ok
Test #29:
score: 0
Accepted
time: 207ms
memory: 97292kb
input:
7533
output:
YES 6998 7 8 6 7 5 6 4 5 3 4 2 3 1 2 12 13 14 15 12 14 11 12 10 11 9 10 1 9 22 23 21 22 20 21 19 20 18 19 17 18 16 17 26 27 29 30 28 29 26 28 25 26 24 25 16 24 37 38 36 37 35 36 34 35 33 34 32 33 31 32 41 42 40 41 44 45 43 44 40 43 39 40 31 39 52 53 51 52 50 51 49 50 48 49 47 48 46 47 55 56 59 60 58...
result:
ok Everything ok
Test #30:
score: 0
Accepted
time: 209ms
memory: 99480kb
input:
5957
output:
YES 5527 7 8 6 7 5 6 4 5 3 4 2 3 1 2 12 13 14 15 12 14 11 12 10 11 9 10 1 9 22 23 21 22 20 21 19 20 18 19 17 18 16 17 26 27 29 30 28 29 26 28 25 26 24 25 16 24 37 38 36 37 35 36 34 35 33 34 32 33 31 32 41 42 40 41 44 45 43 44 40 43 39 40 31 39 52 53 51 52 50 51 49 50 48 49 47 48 46 47 55 56 59 60 58...
result:
ok Everything ok
Test #31:
score: 0
Accepted
time: 227ms
memory: 115556kb
input:
92651
output:
YES 87225 5 6 4 5 3 4 2 3 1 2 11 12 10 11 9 10 8 9 7 8 1 7 15 16 17 18 15 17 14 15 13 14 1 13 23 24 22 23 21 22 20 21 19 20 29 30 28 29 27 28 26 27 25 26 19 25 32 33 35 36 34 35 32 34 31 32 19 31 41 42 40 41 39 40 38 39 37 38 47 48 46 47 45 46 44 45 43 44 37 43 50 51 49 50 53 54 52 53 49 52 37 49 59...
result:
ok Everything ok
Test #32:
score: 0
Accepted
time: 221ms
memory: 108416kb
input:
58779
output:
YES 55235 5 6 4 5 3 4 2 3 1 2 11 12 10 11 9 10 8 9 7 8 1 7 15 16 17 18 15 17 14 15 13 14 1 13 23 24 22 23 21 22 20 21 19 20 29 30 28 29 27 28 26 27 25 26 19 25 32 33 35 36 34 35 32 34 31 32 19 31 41 42 40 41 39 40 38 39 37 38 47 48 46 47 45 46 44 45 43 44 37 43 50 51 49 50 53 54 52 53 49 52 37 49 59...
result:
ok Everything ok
Test #33:
score: 0
Accepted
time: 211ms
memory: 99384kb
input:
12203
output:
YES 11374 5 6 4 5 3 4 2 3 1 2 8 9 10 11 8 10 7 8 1 7 12 13 15 16 14 15 12 14 1 12 20 21 19 20 18 19 17 18 25 26 24 25 23 24 22 23 17 22 31 32 30 31 29 30 28 29 27 28 17 27 36 37 35 36 34 35 33 34 41 42 40 41 39 40 38 39 33 38 45 46 47 48 45 47 44 45 43 44 33 43 52 53 51 52 50 51 49 50 57 58 56 57 55...
result:
ok Everything ok
Test #34:
score: 0
Accepted
time: 225ms
memory: 106404kb
input:
55627
output:
YES 52258 5 6 4 5 3 4 2 3 1 2 11 12 10 11 9 10 8 9 7 8 1 7 15 16 17 18 15 17 14 15 13 14 1 13 23 24 22 23 21 22 20 21 19 20 29 30 28 29 27 28 26 27 25 26 19 25 32 33 35 36 34 35 32 34 31 32 19 31 41 42 40 41 39 40 38 39 37 38 47 48 46 47 45 46 44 45 43 44 37 43 50 51 49 50 53 54 52 53 49 52 37 49 59...
result:
ok Everything ok
Test #35:
score: 0
Accepted
time: 234ms
memory: 115548kb
input:
99051
output:
YES 93269 5 6 4 5 3 4 2 3 1 2 11 12 10 11 9 10 8 9 7 8 1 7 15 16 17 18 15 17 14 15 13 14 1 13 23 24 22 23 21 22 20 21 19 20 29 30 28 29 27 28 26 27 25 26 19 25 32 33 35 36 34 35 32 34 31 32 19 31 41 42 40 41 39 40 38 39 37 38 47 48 46 47 45 46 44 45 43 44 37 43 50 51 49 50 53 54 52 53 49 52 37 49 59...
result:
ok Everything ok
Test #36:
score: 0
Accepted
time: 339ms
memory: 176204kb
input:
811713
output:
YES 770513 10 11 9 10 8 9 7 8 6 7 5 6 4 5 3 4 2 3 1 2 18 19 20 21 18 20 17 18 16 17 15 16 14 15 13 14 12 13 1 12 31 32 30 31 29 30 28 29 27 28 26 27 25 26 24 25 23 24 22 23 38 39 41 42 40 41 38 40 37 38 36 37 35 36 34 35 33 34 22 33 52 53 51 52 50 51 49 50 48 49 47 48 46 47 45 46 44 45 43 44 59 60 5...
result:
ok Everything ok
Test #37:
score: 0
Accepted
time: 299ms
memory: 160108kb
input:
544133
output:
YES 515717 6 7 5 6 4 5 3 4 2 3 1 2 10 11 12 13 10 12 9 10 8 9 1 8 19 20 18 19 17 18 16 17 15 16 14 15 1 14 26 27 25 26 24 25 23 24 22 23 21 22 30 31 32 33 30 32 29 30 28 29 21 28 37 38 39 40 37 39 36 37 35 36 34 35 21 34 46 47 45 46 44 45 43 44 42 43 41 42 50 51 52 53 50 52 49 50 48 49 41 48 56 57 5...
result:
ok Everything ok
Test #38:
score: 0
Accepted
time: 277ms
memory: 145960kb
input:
276553
output:
YES 261516 6 7 5 6 4 5 3 4 2 3 1 2 10 11 12 13 10 12 9 10 8 9 1 8 19 20 18 19 17 18 16 17 15 16 14 15 1 14 26 27 25 26 24 25 23 24 22 23 21 22 30 31 32 33 30 32 29 30 28 29 21 28 37 38 39 40 37 39 36 37 35 36 34 35 21 34 46 47 45 46 44 45 43 44 42 43 41 42 50 51 52 53 50 52 49 50 48 49 41 48 56 57 5...
result:
ok Everything ok
Test #39:
score: 0
Accepted
time: 346ms
memory: 175312kb
input:
736904
output:
YES 699266 10 11 9 10 8 9 7 8 6 7 5 6 4 5 3 4 2 3 1 2 18 19 20 21 18 20 17 18 16 17 15 16 14 15 13 14 12 13 1 12 31 32 30 31 29 30 28 29 27 28 26 27 25 26 24 25 23 24 22 23 38 39 41 42 40 41 38 40 37 38 36 37 35 36 34 35 33 34 22 33 52 53 51 52 50 51 49 50 48 49 47 48 46 47 45 46 44 45 43 44 59 60 5...
result:
ok Everything ok
Test #40:
score: 0
Accepted
time: 407ms
memory: 183676kb
input:
1000000
output:
YES 949834 10 11 9 10 8 9 7 8 6 7 5 6 4 5 3 4 2 3 1 2 18 19 20 21 18 20 17 18 16 17 15 16 14 15 13 14 12 13 1 12 31 32 30 31 29 30 28 29 27 28 26 27 25 26 24 25 23 24 22 23 38 39 41 42 40 41 38 40 37 38 36 37 35 36 34 35 33 34 22 33 52 53 51 52 50 51 49 50 48 49 47 48 46 47 45 46 44 45 43 44 59 60 5...
result:
ok Everything ok
Extra Test:
score: 0
Extra Test Passed