Submission #1156076

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156076		Math4Life2020	Table Tennis (JOI24_tabletennis)	C++20	100 / 100	807 ms	685436 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,v2,v3;
    pii pbk = v0.back();
    ll szl = v0.size()-1;
    ll num1 = pbk.first;
    ll x0 = pbk.second;
    ll DMAX = -1;
    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});
        DMAX = cdeg;
    }
    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;
        if (cdeg==DMAX) {
            v3.push_back({cdeg-1,xc});
        } else {
            v2.push_back({cdeg-1,xc});
        }
    }
    vector<pii> vf;
    for (pii p0: v1) {
        if (p0.first!=DMAX) {
            vf.push_back(p0);
        }
    }
    for (pii p0: v3) {
        vf.push_back(p0);
    }
    for (pii p0: v1) {
        if (p0.first==DMAX) {
            vf.push_back(p0);
        }
    }
    for (pii p0: v2) {
        vf.push_back(p0);
    }
    prc(vf);
}

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 = N/2; //# of pairs left
        ll JMAX = N/2-1;
        while (npl>0) {
            assert(ndel>=0);
            //cout << "npl="<<npl<<"\n";
            //cout << "ndel="<<ndel<<"\n";
            if (ndel==0) {
                //cout << "0blk\n";
                vdegs.push_back(N/2);
                vdegs.push_back((N/2)-1);
                npl--;
            } else if (ndel==5) {
                //cout << "5blk\n";
                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);
                //cout << "1blk\n";
                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-=1;
            } else {
                while (ndel<(JMAX*(JMAX+1))) {
                    JMAX--;
                }
                npl-=1;
                ndel-=(JMAX*(JMAX+1));
                //cout << "jblk,val="<<(JMAX*(JMAX+1))<<"\n";
                vdegs.push_back((N/2)+JMAX);
                vdegs.push_back((N/2)-1-JMAX);
                if (JMAX>2) {
                    JMAX--;
                }
            }
        }
        //exit(0);
        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});
            //cout << "vdegQ term: "<<vdegs[i]<<","<<i<<"\n";
        }
        //exit(0);
        sort(vdegQ.begin(),vdegQ.end());
        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) {
            assert(ndel>=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);
        sort(vdegQ.begin(),vdegQ.end());
        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: 5 / 5
• Subtask 2: 4 / 4
• Subtask 3: 23 / 23
• Subtask 4: 30 / 30
• Subtask 5: 15 / 15
• Subtask 6: 23 / 23