QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#414497#8208. Beer Circuitsucup-team1231#WA 250ms257292kbC++203.1kb2024-05-19 04:35:492024-05-19 04:35:51

Judging History

你现在查看的是最新测评结果

  • [2024-05-19 04:35:51]
  • 评测
  • 测评结果:WA
  • 用时:250ms
  • 内存:257292kb
  • [2024-05-19 04:35:49]
  • 提交

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