Submission #1161840

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161840		tosivanmak	Table Tennis (JOI24_tabletennis)	C++20	100 / 100	487 ms	38164 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define ll long long

// I love table tennis!
ll ans[5005];
ll id[5005],od[5005];
void solve(){
    ll n,k;
    cin>>n>>k;
    if(ans[n]<k){
        cout<<"No\n"; return;
    }
    if(k==0){
        cout<<"Yes\n";
        for(int i=1;i<=n-1;i++){
            for(int j=1;j<=i;j++){
               cout<<"1";
            }
            cout<<'\n';
        }
        return;
    }
    cout<<"Yes\n";
    ll indeg[n+2],outdeg[n+2];
    bool edge[n+2][n+2];
    for(int i=0;i<n+2;i++){
        indeg[i]=outdeg[i]=0;
    }
    ll rn;
    for(int i=n;i>=2;i--){
        if(ans[i]<k){rn=i+1; break;}
    }
    for(int i=1;i<=rn;i++){
        if(i==1){
            continue;
        }
        ll mx,mn;
        for(int j=1;j<i;j++){
            if(j==1)mx=indeg[j],mn=indeg[j];
            else mx=max(mx,indeg[j]),mn=min(mn,indeg[j]);
        }
        if(mx==mn){
            for(int j=1;j<=(i-1)/2;j++){indeg[j]++,outdeg[i]++; edge[i][j]=1; edge[j][i]=0;}
            for(int j=(i-1)/2+1;j<i;j++){outdeg[j]++,indeg[i]++; edge[j][i]=1; edge[i][j]=0;}
        }
        else{
            for(int j=1;j<i;j++){
                if(indeg[j]==mn){indeg[j]++,outdeg[i]++; edge[i][j]=1; edge[j][i]=0;}
                else{indeg[i]++,outdeg[j]++; edge[j][i]=1; edge[i][j]=0;}
            }
        }
    }
    set<ll>st;
    vector<ll>degs[n+5];
    for(int i=1;i<=rn;i++){
        // cout<<id[i]<<" ";
        degs[indeg[i]].push_back(i);
    }
    for(int i=1;i<=rn;i++){
        if(degs[i].size()>=2){
            st.insert(i);
        }
    }
    ll diff=ans[rn]-k;
    for(int i=1;i<=diff;i++){
        ll lol=*st.begin();
        ll cur1=degs[lol][degs[lol].size()-1]; degs[lol].pop_back();
        ll cur2=degs[lol][degs[lol].size()-1]; degs[lol].pop_back();
        if(degs[lol].size()<2){
            st.erase(st.find(lol));
        }
        if(edge[cur1][cur2]){
            edge[cur1][cur2]=0; edge[cur2][cur1]=1;
            degs[lol+1].push_back(cur1);
            degs[lol-1].push_back(cur2);
            if(degs[lol+1].size()>=2)st.insert(lol+1);
            if(degs[lol-1].size()>=2)st.insert(lol-1);
        }
        else{
            edge[cur1][cur2]=1; edge[cur2][cur1]=0;
            degs[lol+1].push_back(cur2);
            degs[lol-1].push_back(cur1);
            if(degs[lol+1].size()>=2)st.insert(lol+1);
            if(degs[lol-1].size()>=2)st.insert(lol-1);
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==j)continue;
            if(i<=rn&&j<=rn)continue;
            else{
                if(i<j)edge[i][j]=1;
                else edge[i][j]=0;
            }
        }
    }
    for(int i=2;i<=n;i++){
        for(int j=1;j<i;j++){
            if(edge[i][j])cout<<1;
            else cout<<0;
        }
        cout<<'\n';
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    for(int i=1;i<=5000;i++){
        if(i==1)continue;
        ll mx,mn;
        for(int j=1;j<i;j++){
            if(j==1)mx=id[j],mn=id[j];
            else mx=max(mx,id[j]),mn=min(mn,id[j]);
        }
        if(mx==mn){
            for(int j=1;j<=(i-1)/2;j++)id[j]++,od[i]++;
            for(int j=(i-1)/2+1;j<i;j++)od[j]++,id[i]++;
        }
        else{
            for(int j=1;j<i;j++){
                if(id[j]==mn)id[j]++,od[i]++;
                else id[i]++,od[j]++;
            }
        }
        ll tot=0;
        ans[i]=(ll)i*((ll)i-(ll)1)*((ll)i-(ll)2)/(ll)6;
        for(int j=1;j<=i;j++){
            tot+=(id[j]-1)*id[j]/2; tot+=(od[j]-1)*(od[j])/2;
        }
        ans[i]-=tot/2;
    }
    ll t;
    cin>>t;
    while(t--)solve();
}

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