QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#414503 | #8215. Isomorphic Delight | ucup-team1231# | ML | 265ms | 258088kb | C++20 | 3.3kb | 2024-05-19 05:15:11 | 2024-05-19 05:15:13 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
vector<int> ch[4500005];
int siz[4500005];
int beg[5555], cnt, sz;
int arr[5555], len;
void gen_rooted(int sum, int pre) {
if(sum == 0) {
siz[cnt] = sz;
// if(cnt%100000==0) cerr<<cnt<<"+\n";
ch[cnt++] = vector<int>(arr, arr + len);
return;
}
for(int i = pre + 1; i < cnt && siz[i] <= sum; i++) {
if(siz[i] < sum && siz[i] > sum / 2) i = beg[sum];
if(sum!=siz[i]&&(i==cnt-1||siz[i+1]+siz[i]>sum)) continue;
arr[len++] = i;
gen_rooted(sum - siz[i], i);
len--;
}
}
void output(int v) {
putchar('(');
for(auto u : ch[v]) output(u);
putchar(')');
}
bool isok[4500005];
map<int,int> poo;
vector<int> goods[100055];
void init() {
int N = 0;
int pos = 0;
for(sz = 1; sz<=22; sz++) {
beg[sz] = cnt;
gen_rooted(sz - 1, -1);
// printf(" %d,%d\n", sz,N);
for(int i = beg[sz]; i < cnt; i++) {
assert(siz[i]>=siz[i-1]);
bool ok = true;
assert(is_sorted(ch[i].begin(),ch[i].end()));
if(!ch[i].empty() && siz[ch[i].back()] > siz[i] / 2) ok = false;
else if(!ch[i].empty() && siz[ch[i].back()] * 2 == siz[i]) {
vector<int> vec(ch[i].begin(), ch[i].end() - 1);
while(ch[pos] != vec) pos++;
assert(ch[pos]==vec);
// cerr<<pos<<","<<ch[i].back()<<"+\n";
if(pos >= ch[i].back()) ok = false;
}
isok[i] = ok;
if(isok[i]) {
N += sz;
goods[sz].push_back(i);
poo[sz]++;
}
}
cerr<<sz<<","<<cnt<<","<<N<<"+\n";
}
}
#define SZ 1000999
pair<int,int> f[SZ];
int a[SZ];
void knapsack() {
memset(a,-127/3,sizeof a);
a[0]=0;
for(auto g:poo) {
auto pack=[&](int x,int y) {
for(int u=SZ-1;u>=x*y;--u) {
int v=a[u-x*y]+y;
if(v<=a[u]) continue;
a[u]=v;
f[u]=make_pair(x,y);
}
};
int x=g.first,y=g.second;
for(int u=0;(1<<u)<=y;++u) {
y-=1<<u;
pack(x,1<<u);
}
pack(x,y);
}
}
int main() {
init();
// cerr<<"++\n";
int n;
scanf("%d", &n);
knapsack();
if(n==6) {
printf(R"(YES
6
1 2
2 3
1 3
3 4
2 5
5 6)");
return 0;
}
if(a[n]<0) {
puts("NO");
return 0;
}
map<int,int> cnt;
int n_=n;
while(n) {
int x=f[n].first,y=f[n].second;
cnt[x]+=y; n-=x*y;
}
printf("YES\n");
int N=0;
vector<pair<int,int>> eg;
function<void(int,int)> dfs;
dfs = [&] (int x,int fa) {
int X=++N;
if(fa) eg.push_back({N,fa});
for(auto c:ch[x]) dfs(c,X);
};
for(auto g:cnt) {
// cerr<<g.first<<"x"<<g.second<<"\n";
auto&V=goods[g.first];
while(g.second--) {
assert(V.size());
int x=V.back();
dfs(x,0);
V.pop_back();
}
}
// cerr<<N<<"\n";
assert(N==n_);
printf("%d\n",int(eg.size()));
for(auto e:eg) printf("%d %d\n",e.first,e.second);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 231ms
memory: 257516kb
input:
1
output:
YES 0
result:
ok Everything ok
Test #2:
score: 0
Accepted
time: 249ms
memory: 257208kb
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: 242ms
memory: 257336kb
input:
4
output:
NO
result:
ok Everything ok
Test #4:
score: 0
Accepted
time: 226ms
memory: 257060kb
input:
2
output:
NO
result:
ok Everything ok
Test #5:
score: 0
Accepted
time: 233ms
memory: 257172kb
input:
3
output:
NO
result:
ok Everything ok
Test #6:
score: 0
Accepted
time: 234ms
memory: 257056kb
input:
5
output:
NO
result:
ok Everything ok
Test #7:
score: 0
Accepted
time: 256ms
memory: 257516kb
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: 252ms
memory: 257240kb
input:
8
output:
YES 6 3 2 4 2 5 4 6 2 7 6 8 7
result:
ok Everything ok
Test #9:
score: 0
Accepted
time: 249ms
memory: 257232kb
input:
9
output:
YES 7 3 2 4 2 5 4 6 2 7 6 8 7 9 8
result:
ok Everything ok
Test #10:
score: 0
Accepted
time: 265ms
memory: 255212kb
input:
10
output:
YES 8 3 2 4 3 5 3 6 5 7 2 8 7 9 8 10 9
result:
ok Everything ok
Test #11:
score: 0
Accepted
time: 231ms
memory: 257316kb
input:
11
output:
YES 9 3 2 4 3 5 3 6 5 7 2 8 7 9 8 10 9 11 10
result:
ok Everything ok
Test #12:
score: 0
Accepted
time: 263ms
memory: 257500kb
input:
12
output:
YES 10 3 2 4 3 5 4 6 4 7 6 8 2 9 8 10 9 11 10 12 11
result:
ok Everything ok
Test #13:
score: 0
Accepted
time: 244ms
memory: 257236kb
input:
13
output:
YES 11 3 2 4 3 5 4 6 4 7 6 8 2 9 8 10 9 11 10 12 11 13 12
result:
ok Everything ok
Test #14:
score: 0
Accepted
time: 246ms
memory: 257572kb
input:
14
output:
YES 12 3 2 4 3 5 4 6 5 7 5 8 7 9 2 10 9 11 10 12 11 13 12 14 13
result:
ok Everything ok
Test #15:
score: 0
Accepted
time: 261ms
memory: 257184kb
input:
15
output:
YES 13 2 1 3 1 4 3 5 1 6 5 7 6 9 8 10 8 11 10 12 8 13 12 14 13 15 14
result:
ok Everything ok
Test #16:
score: 0
Accepted
time: 251ms
memory: 257408kb
input:
16
output:
YES 13 3 2 4 2 5 4 6 2 7 6 8 7 10 9 11 9 12 11 13 9 14 13 15 14 16 15
result:
ok Everything ok
Test #17:
score: 0
Accepted
time: 261ms
memory: 255444kb
input:
17
output:
YES 14 3 2 4 2 5 4 6 2 7 6 8 7 10 9 11 10 12 10 13 12 14 9 15 14 16 15 17 16
result:
ok Everything ok
Test #18:
score: 0
Accepted
time: 243ms
memory: 255280kb
input:
18
output:
YES 15 3 2 4 2 5 4 6 2 7 6 8 7 9 8 11 10 12 11 13 11 14 13 15 10 16 15 17 16 18 17
result:
ok Everything ok
Test #19:
score: 0
Accepted
time: 211ms
memory: 257316kb
input:
19
output:
YES 16 3 2 4 3 5 3 6 5 7 2 8 7 9 8 10 9 12 11 13 11 14 13 15 14 16 11 17 16 18 17 19 18
result:
ok Everything ok
Test #20:
score: 0
Accepted
time: 243ms
memory: 257512kb
input:
598
output:
YES 544 3 2 4 2 5 4 6 2 7 6 8 7 9 8 11 10 12 11 13 11 14 13 15 10 16 15 17 16 18 17 20 19 21 19 22 21 23 22 24 19 25 24 26 25 27 26 29 28 30 28 31 30 32 31 33 28 34 33 35 33 36 35 38 37 39 38 40 38 41 40 42 37 43 42 44 43 45 44 46 45 48 47 49 48 50 47 51 50 52 51 53 47 54 53 55 54 56 55 58 57 59 58 ...
result:
ok Everything ok
Test #21:
score: 0
Accepted
time: 237ms
memory: 257232kb
input:
245
output:
YES 221 2 1 3 1 4 3 5 1 6 5 7 6 9 8 10 8 11 10 12 8 13 12 14 13 15 14 17 16 18 17 19 17 20 19 21 16 22 21 23 22 24 23 26 25 27 25 28 27 29 28 30 25 31 30 32 31 33 32 35 34 36 34 37 36 38 37 39 34 40 39 41 39 42 41 44 43 45 44 46 44 47 46 48 43 49 48 50 49 51 50 52 51 54 53 55 54 56 53 57 56 58 57 59...
result:
ok Everything ok
Test #22:
score: 0
Accepted
time: 239ms
memory: 255268kb
input:
793
output:
YES 724 3 2 4 2 5 4 6 2 7 6 8 7 9 8 11 10 12 11 13 11 14 13 15 10 16 15 17 16 18 17 20 19 21 19 22 21 23 22 24 19 25 24 26 25 27 26 29 28 30 28 31 30 32 31 33 28 34 33 35 33 36 35 38 37 39 38 40 38 41 40 42 37 43 42 44 43 45 44 46 45 48 47 49 48 50 47 51 50 52 51 53 47 54 53 55 54 56 55 58 57 59 58 ...
result:
ok Everything ok
Test #23:
score: 0
Accepted
time: 242ms
memory: 257184kb
input:
133
output:
YES 119 3 2 4 3 5 3 6 5 7 2 8 7 9 8 10 9 12 11 13 11 14 13 15 14 16 11 17 16 18 17 19 18 21 20 22 20 23 22 24 23 25 20 26 25 27 25 28 27 30 29 31 30 32 30 33 32 34 29 35 34 36 35 37 36 38 37 40 39 41 40 42 39 43 42 44 43 45 39 46 45 47 46 48 47 50 49 51 50 52 49 53 52 54 53 55 49 56 55 57 55 58 57 6...
result:
ok Everything ok
Test #24:
score: 0
Accepted
time: 241ms
memory: 257456kb
input:
681
output:
YES 620 3 2 4 2 5 4 6 2 7 6 8 7 10 9 11 9 12 11 13 9 14 13 15 14 16 15 18 17 19 18 20 18 21 20 22 17 23 22 24 23 25 24 27 26 28 26 29 28 30 29 31 26 32 31 33 32 34 33 36 35 37 35 38 37 39 38 40 35 41 40 42 40 43 42 45 44 46 45 47 45 48 47 49 44 50 49 51 50 52 51 53 52 55 54 56 55 57 54 58 57 59 58 6...
result:
ok Everything ok
Test #25:
score: 0
Accepted
time: 260ms
memory: 255160kb
input:
922
output:
YES 843 3 2 4 2 5 4 6 2 7 6 8 7 9 8 11 10 12 11 13 11 14 13 15 10 16 15 17 16 18 17 20 19 21 19 22 21 23 22 24 19 25 24 26 25 27 26 29 28 30 28 31 30 32 31 33 28 34 33 35 33 36 35 38 37 39 38 40 38 41 40 42 37 43 42 44 43 45 44 46 45 48 47 49 48 50 47 51 50 52 51 53 47 54 53 55 54 56 55 58 57 59 58 ...
result:
ok Everything ok
Test #26:
score: 0
Accepted
time: 246ms
memory: 257516kb
input:
876
output:
YES 800 3 2 4 2 5 4 6 2 7 6 8 7 10 9 11 9 12 11 13 9 14 13 15 14 16 15 18 17 19 18 20 18 21 20 22 17 23 22 24 23 25 24 27 26 28 26 29 28 30 29 31 26 32 31 33 32 34 33 36 35 37 35 38 37 39 38 40 35 41 40 42 40 43 42 45 44 46 45 47 45 48 47 49 44 50 49 51 50 52 51 53 52 55 54 56 55 57 54 58 57 59 58 6...
result:
ok Everything ok
Test #27:
score: 0
Accepted
time: 246ms
memory: 257232kb
input:
7740
output:
YES 7191 3 2 4 2 5 4 6 2 7 6 8 7 10 9 11 9 12 11 13 9 14 13 15 14 16 15 18 17 19 18 20 18 21 20 22 17 23 22 24 23 25 24 27 26 28 26 29 28 30 29 31 26 32 31 33 32 34 33 36 35 37 35 38 37 39 38 40 35 41 40 42 40 43 42 45 44 46 45 47 45 48 47 49 44 50 49 51 50 52 51 53 52 55 54 56 55 57 54 58 57 59 58 ...
result:
ok Everything ok
Test #28:
score: 0
Accepted
time: 256ms
memory: 257232kb
input:
2460
output:
YES 2268 3 2 4 2 5 4 6 2 7 6 8 7 9 8 11 10 12 11 13 11 14 13 15 10 16 15 17 16 18 17 20 19 21 19 22 21 23 22 24 19 25 24 26 25 27 26 29 28 30 28 31 30 32 31 33 28 34 33 35 33 36 35 38 37 39 38 40 38 41 40 42 37 43 42 44 43 45 44 46 45 48 47 49 48 50 47 51 50 52 51 53 47 54 53 55 54 56 55 58 57 59 58...
result:
ok Everything ok
Test #29:
score: 0
Accepted
time: 259ms
memory: 255480kb
input:
7533
output:
YES 6998 3 2 4 2 5 4 6 2 7 6 8 7 10 9 11 9 12 11 13 9 14 13 15 14 16 15 18 17 19 18 20 18 21 20 22 17 23 22 24 23 25 24 27 26 28 26 29 28 30 29 31 26 32 31 33 32 34 33 36 35 37 35 38 37 39 38 40 35 41 40 42 40 43 42 45 44 46 45 47 45 48 47 49 44 50 49 51 50 52 51 53 52 55 54 56 55 57 54 58 57 59 58 ...
result:
ok Everything ok
Test #30:
score: 0
Accepted
time: 250ms
memory: 257208kb
input:
5957
output:
YES 5527 3 2 4 2 5 4 6 2 7 6 8 7 10 9 11 9 12 11 13 9 14 13 15 14 16 15 18 17 19 18 20 18 21 20 22 17 23 22 24 23 25 24 27 26 28 26 29 28 30 29 31 26 32 31 33 32 34 33 36 35 37 35 38 37 39 38 40 35 41 40 42 40 43 42 45 44 46 45 47 45 48 47 49 44 50 49 51 50 52 51 53 52 55 54 56 55 57 54 58 57 59 58 ...
result:
ok Everything ok
Test #31:
score: 0
Accepted
time: 259ms
memory: 258064kb
input:
92651
output:
YES 87225 3 2 4 2 5 4 6 2 7 6 8 7 10 9 11 10 12 10 13 12 14 9 15 14 16 15 17 16 19 18 20 18 21 20 22 21 23 18 24 23 25 24 26 25 28 27 29 27 30 29 31 30 32 27 33 32 34 32 35 34 37 36 38 37 39 37 40 39 41 36 42 41 43 42 44 43 45 44 47 46 48 47 49 46 50 49 51 50 52 46 53 52 54 53 55 54 57 56 58 57 59 5...
result:
ok Everything ok
Test #32:
score: 0
Accepted
time: 252ms
memory: 257596kb
input:
58779
output:
YES 55235 3 2 4 2 5 4 6 2 7 6 8 7 9 8 11 10 12 11 13 11 14 13 15 10 16 15 17 16 18 17 20 19 21 19 22 21 23 22 24 19 25 24 26 25 27 26 29 28 30 28 31 30 32 31 33 28 34 33 35 33 36 35 38 37 39 38 40 38 41 40 42 37 43 42 44 43 45 44 46 45 48 47 49 48 50 47 51 50 52 51 53 47 54 53 55 54 56 55 58 57 59 5...
result:
ok Everything ok
Test #33:
score: 0
Accepted
time: 245ms
memory: 257380kb
input:
12203
output:
YES 11374 3 2 4 2 5 4 6 2 7 6 8 7 10 9 11 10 12 10 13 12 14 9 15 14 16 15 17 16 19 18 20 18 21 20 22 21 23 18 24 23 25 24 26 25 28 27 29 27 30 29 31 30 32 27 33 32 34 32 35 34 37 36 38 37 39 37 40 39 41 36 42 41 43 42 44 43 45 44 47 46 48 47 49 46 50 49 51 50 52 46 53 52 54 53 55 54 57 56 58 57 59 5...
result:
ok Everything ok
Test #34:
score: 0
Accepted
time: 232ms
memory: 257732kb
input:
55627
output:
YES 52258 3 2 4 2 5 4 6 2 7 6 8 7 9 8 11 10 12 11 13 11 14 13 15 10 16 15 17 16 18 17 20 19 21 19 22 21 23 22 24 19 25 24 26 25 27 26 29 28 30 28 31 30 32 31 33 28 34 33 35 33 36 35 38 37 39 38 40 38 41 40 42 37 43 42 44 43 45 44 46 45 48 47 49 48 50 47 51 50 52 51 53 47 54 53 55 54 56 55 58 57 59 5...
result:
ok Everything ok
Test #35:
score: 0
Accepted
time: 262ms
memory: 258088kb
input:
99051
output:
YES 93269 3 2 4 2 5 4 6 2 7 6 8 7 10 9 11 9 12 11 13 9 14 13 15 14 16 15 18 17 19 18 20 18 21 20 22 17 23 22 24 23 25 24 27 26 28 26 29 28 30 29 31 26 32 31 33 32 34 33 36 35 37 35 38 37 39 38 40 35 41 40 42 40 43 42 45 44 46 45 47 45 48 47 49 44 50 49 51 50 52 51 53 52 55 54 56 55 57 54 58 57 59 58...
result:
ok Everything ok
Test #36:
score: -100
Memory Limit Exceeded
input:
811713
output:
YES 770513 3 2 4 2 5 4 6 2 7 6 8 7 9 8 11 10 12 11 13 11 14 13 15 10 16 15 17 16 18 17 20 19 21 19 22 21 23 22 24 19 25 24 26 25 27 26 29 28 30 28 31 30 32 31 33 28 34 33 35 33 36 35 38 37 39 38 40 38 41 40 42 37 43 42 44 43 45 44 46 45 48 47 49 48 50 47 51 50 52 51 53 47 54 53 55 54 56 55 58 57 59 ...