QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#414499 | #8215. Isomorphic Delight | ucup-team1231# | WA | 278ms | 257452kb | C++20 | 3.1kb | 2024-05-19 04:58:08 | 2024-05-19 04:58:08 |
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++) {
bool ok = true;
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++;
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: 262ms
memory: 257180kb
input:
1
output:
YES 0
result:
ok Everything ok
Test #2:
score: 0
Accepted
time: 248ms
memory: 257096kb
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: 253ms
memory: 255204kb
input:
4
output:
NO
result:
ok Everything ok
Test #4:
score: 0
Accepted
time: 226ms
memory: 255080kb
input:
2
output:
NO
result:
ok Everything ok
Test #5:
score: 0
Accepted
time: 254ms
memory: 257180kb
input:
3
output:
NO
result:
ok Everything ok
Test #6:
score: 0
Accepted
time: 248ms
memory: 255132kb
input:
5
output:
NO
result:
ok Everything ok
Test #7:
score: 0
Accepted
time: 278ms
memory: 257244kb
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: 263ms
memory: 257444kb
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: 237ms
memory: 257160kb
input:
9
output:
YES 7 3 2 4 3 5 4 6 2 7 6 8 6 9 8
result:
ok Everything ok
Test #10:
score: 0
Accepted
time: 255ms
memory: 257228kb
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: 259ms
memory: 257184kb
input:
11
output:
YES 9 3 2 4 3 5 4 6 5 7 2 8 7 9 8 10 8 11 10
result:
ok Everything ok
Test #12:
score: 0
Accepted
time: 238ms
memory: 255400kb
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: 235ms
memory: 257192kb
input:
13
output:
YES 11 3 2 4 3 5 4 6 5 7 6 8 2 9 8 10 9 11 10 12 10 13 12
result:
ok Everything ok
Test #14:
score: 0
Accepted
time: 241ms
memory: 255196kb
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: 240ms
memory: 255152kb
input:
15
output:
YES 13 2 1 3 1 4 3 5 1 6 5 7 6 9 8 10 9 11 10 12 8 13 12 14 12 15 14
result:
ok Everything ok
Test #16:
score: 0
Accepted
time: 260ms
memory: 257184kb
input:
16
output:
YES 13 3 2 4 2 5 4 6 2 7 6 8 7 10 9 11 10 12 11 13 9 14 13 15 13 16 15
result:
ok Everything ok
Test #17:
score: -100
Wrong Answer
time: 243ms
memory: 257452kb
input:
17
output:
YES 14 3 2 4 3 5 4 6 2 7 6 8 6 9 8 11 10 12 10 13 12 14 10 15 14 16 15 17 16
result:
wrong answer Not asymmetric