Submission #1306227

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306227		jojeonghoon	Table Tennis (JOI24_tabletennis)	C++20	100 / 100	539 ms	37820 KiB

Main

#include <iostream>
#include <vector>
#include <set>
#include<algorithm>
#include<queue>
#include<map>
#include<math.h>
#include<assert.h>
#include<random>
#define ll long long
#define int ll
#define i32 __int32_t
#define i64 __int64_t
#define i128 __int128_t
#define db double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define bk back()
#define bg begin()
#define ed end()
#define vi vector<int>
#define vii vector<pii>
#define rep(i,a,b) for(int i=(a); i<=(b); i++)
#define all(x) (x).begin(), (x).end()
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("avx,avx2,fma")
using namespace std;

int N,M;
int F(int k, int n){
    return (k/n)*(k/n+1)/2 * (k%n) + (k/n)*(k/n-1)/2 * (n-k%n);
}
int a[5050];
pii v[5050];
bool ans[5050][5050];

void solve(){
    cin>>N>>M;
    M= N*(N-1)*(N-2)/6 - M;
    
    int k=N*(N-1)/2;
    
    if(F(k, N)>M){
        cout<<"No\n";
        return;
    }
    
    a[N+1]=N-1;
    for(int i=N; i>1; i--){
        a[i] = a[i+1];
        for(; a[i]>=0; a[i]--){
            if(F(k-a[i], i-1) + a[i]*(a[i]-1)/2 <= M && (k-a[i])>=(i-2)*(i-1)/2){
                break;
            }
        }
        k -= a[i];
        M -= a[i]*(a[i]-1)/2;
    }
    
    a[1]=k;
    k-=a[1];
    M-=a[1]*(a[1]-1)/2;
    
    for(int i=1; i<=N; i++) v[i] = {a[i],i};
    
    rep(i,1,N) rep(j,1,N) ans[i][j]=0;
    
    for(int i=N; i>0; i--){
        for(int j=1; j<=v[i].first; j++){
            ans[v[j].second][v[i].second]=1^(v[i].second<v[j].second);
            ans[v[i].second][v[j].second]=1^(v[i].second<v[j].second);
        }
        for(int j=v[i].first+1; j<i ;j++){
            ans[v[j].second][v[i].second]=(v[i].second<v[j].second);
            ans[v[i].second][v[j].second]=(v[i].second<v[j].second);
            v[j].first--;
        }
        sort(v+1, v+i);
    }
    cout<<"Yes\n";
    for(int i=2; i<=N; i++){
        for(int j=1; j<i; j++) cout<<ans[i][j];
        cout<<"\n";
    }
}

signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int tc;cin>>tc;while(tc--)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