QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#414497 | #8208. Beer Circuits | ucup-team1231# | WA | 250ms | 257292kb | C++20 | 3.1kb | 2024-05-19 04:35:49 | 2024-05-19 04:35:51 |
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: 0
Wrong Answer
time: 250ms
memory: 257292kb
input:
3 3 0 0 2 2 1000000000 1000000000
output:
NO
result:
wrong output format Expected integer, but "NO" found