Submission #1156061

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156061		Math4Life2020	Table Tennis (JOI24_tabletennis)	C++20	0 / 100	0 ms	328 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;

vector<vector<bool>> ans;

void prc(vector<pii> v0) { //has this outdegree
    if (v0.size()<=1) {
        return;
    }
    sort(v0.begin(),v0.end());
    vector<pii> v1;
    pii pbk = v0.back();
    ll szl = v0.size()-1;
    ll num1 = pbk.first;
    ll x0 = pbk.second;
    for (ll i=0;i<num1;i++) {
        ll xc = v0[i].second; ll cdeg = v0[i].first;
        ans[x0][xc]=1;
        ans[xc][x0]=0;
        v1.push_back({cdeg,xc});
    }
    for (ll i=num1;i<szl;i++) {
        ll xc = v0[i].second; ll cdeg = v0[i].first;
        ans[x0][xc]=0;
        ans[xc][x0]=1;
        v1.push_back({cdeg-1,xc});
    }
    prc(v1);
}

void solve(ll N, ll M) {
    ans.clear();
    ll Mmax = (N*(N-1)*(N-2))/6;
    // ll flr = (N-1)/2;
    // Mmax -= N*(flr*(flr-1))/2;
    if (N%2==0) {
        Mmax-=(N/2)*((N/2)*(N/2-1))/2;
        Mmax-=(N/2)*((N/2-2)*(N/2-1))/2;
    } else {
        Mmax-=N*((N/2)*(N/2-1))/2;
    }
    //cout << "M,Mmax="<<M<<","<<Mmax<<"\n";
    // exit(0);
    if (M>Mmax) {
        cout << "No\n";
        return;
    }
    if (N%2==0) {
        cout << "Yes\n";
        vector<ll> vdegs;
        ll ndel = Mmax-M; //# to delete
        ll npl = M; //# of pairs left
        ll JMAX = N/2;
        while (npl>0) {
            if (ndel==0) {
                vdegs.push_back(N/2);
                vdegs.push_back((N/2)-1);
                npl--;
            } else if (ndel==5) {
                vdegs.push_back((N/2)-2);
                vdegs.push_back((N/2)-2);
                vdegs.push_back((N/2));
                vdegs.push_back((N/2)+2);
                npl-=2;
                ndel-=5;
            } else if (ndel==1) {
                assert(npl>=2);
                vdegs.push_back((N/2)-1);
                vdegs.push_back((N/2)-1);
                vdegs.push_back((N/2)-1);
                vdegs.push_back((N/2)+1);
                npl-=2;
                ndel-=5;
            } else {
                while (ndel<(JMAX*(JMAX-1))) {
                    JMAX--;
                }
                npl-=1;
                ndel-=(JMAX*(JMAX-1));
                vdegs.push_back((N/2)+JMAX);
                vdegs.push_back((N/2)-1-JMAX);
                if (JMAX>2) {
                    JMAX--;
                }
            }
        }
        assert(npl==0);
        vector<pii> vdegQ;
        vector<bool> vbk(N,false);
        for (ll i=0;i<N;i++) {
            ans.push_back(vbk);
            vdegQ.push_back({vdegs[i],i});
        }
        prc(vdegQ);
        for (ll i=1;i<N;i++) {
            for (ll j=0;j<i;j++) {
                cout << ans[i][j];
            }
            cout << "\n";
        }
    } else {
        cout << "Yes\n";
        vector<ll> vdegs;
        ll ndel = Mmax-M;
        ll nel = N; //# of elements left
        ll JMAX = (N-1)/2;
        //cout << "ndel,nel="<<ndel<<","<<nel<<"\n"; exit(0);
        while (nel>0) {
            if (ndel==0) {
                vdegs.push_back((N-1)/2);
                nel--;
            } else if (ndel==3) {
                vdegs.push_back((N-1)/2+1);
                vdegs.push_back((N-1)/2+1);
                vdegs.push_back((N-1)/2-2);
                nel-=3;
                ndel-=3;
            } else {
                while (ndel<(JMAX*JMAX)) {
                    JMAX--;
                }
                ndel-=JMAX*JMAX;
                nel-=2;
                vdegs.push_back((N-1)/2+JMAX);
                vdegs.push_back((N-1)/2-JMAX);
                if (JMAX>2) {
                    JMAX--;
                }
            }
        }
        assert(nel==0);
        vector<pii> vdegQ;
        vector<bool> vbk(N,false);
        for (ll i=0;i<N;i++) {
            ans.push_back(vbk);
            vdegQ.push_back({vdegs[i],i});
            //cout << "pair: "<<vdegs[i]<<","<<i<<"\n";
        }
        //exit(0);
        prc(vdegQ);
        for (ll i=1;i<N;i++) {
            for (ll j=0;j<i;j++) {
                cout << ans[i][j];
            }
            cout << "\n";
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
	ll Q; cin >> Q;
    while (Q--) {
        ll N,M; cin >> N >> M;
        solve(N,M);
    }
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 4
• Subtask 3: 0 / 23
• Subtask 4: 0 / 30
• Subtask 5: 0 / 15
• Subtask 6: 0 / 23