Submission #1228606

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228606		noyancanturk	Table Tennis (JOI24_tabletennis)	C++20	0 / 100	555 ms	212556 KiB

Main

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

#define int int64_t
#define pb push_back

const int lim=5100;

int dp[lim];
int n,m;
int e[lim][lim];

void dnc(vector<int>v){
  if(v.size()==2){
    e[v[0]][v[1]]=1;
  }
  if(v.size()<3)return;
  while(v.size()&&m<=dp[v.size()-1]){
    for(int j:v){
      if(j==v.back())break;
      e[v.back()][j]=1;
    }
    v.pop_back();
  }
  int need=v.size();
  int l1=need/3,l2=need/3,l3=need/3;
  if(l1+l2+l3!=need)l1++;
  if(l1+l2+l3!=need)l2++;
  while(l1*l2*l3>m){
    if(l2<l3){
      l1++;
      l3--;
    }else{
      l1++;
      l2--;
    }
  }
  vector<int>g1,g2,g3;
  for(int j=0;j<l1;j++){
    g1.pb(v[j]);
  }
  for(int j=l1;j<l1+l2;j++){
    g2.pb(v[j]);
  }
  for(int j=l1+l2;j<need;j++){
    g3.pb(v[j]);
  }
  m-=l1*l2*l3;
  for(int i:g1){
    for(int j:g2){
      e[i][j]=1;
    }
  }
  for(int i:g2){
    for(int j:g3){
      e[i][j]=1;
    }
  }
  for(int i:g3){
    for(int j:g1){
      e[i][j]=1;
    }
  }
  dnc(g1);
  dnc(g2);
  dnc(g3);
}

void solve(){
  cin>>n>>m;
  if(dp[n]<m){
    cout<<"No\n";
    return;
  }
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      e[i][j]=e[j][i]=0;
    }
  }
  cout<<"Yes\n";
  vector<int>v;
  int need=n;
  while(need&&m<=dp[need-1]){
    need--;
    for(int i=0;i<need;i++){
      e[need][i]=1;
    }
  }
  for(int i=0;i<need;i++){
    v.pb(i);
  }
  dnc(v);
  for(int i=1;i<n;i++){
    for(int j=0;j<i;j++){
      cout<<e[i][j];
    }
    cout<<'\n';
  }
  int cur=0;
  for(int i=0;i<n;i++){
    for(int j=i+1;j<n;j++){
      for(int k=j+1;k<n;k++){
        if((e[i][j]&&e[j][k]&&e[k][i])||(!e[i][j]&&!e[j][k]&&!e[k][i])){
          cur++;
        }
      }
    }
  }
  //cout<<cur<<'\n';
}

signed main(){
  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  dp[1]=dp[2]=0;
  for(int i=3;i<lim;i++){
    int l1=i/3,l2=i/3,l3=i/3;
    if(l1+l2+l3!=i)l1++;
    if(l1+l2+l3!=i)l2++;
    dp[i]=l1*l2*l3+dp[l1]+dp[l2]+dp[l3];
  }
  /*
  for(int i=1;i<lim;i++){
    cout<<dp[i]<<'\n';
  }
  */
  int t;
  cin>>t;
  while(t--){
    solve();
  }
}

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