Submission #1243170

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243170		noyancanturk	Sphinx's Riddle (IOI24_sphinx)	C++20	100 / 100	400 ms	1264 KiB

sphinx

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

const int lim=500;

#define pb push_back
#define ask perform_experiment

int parent[lim];
int find(int i){
  if(i==parent[i])return i;
  return parent[i]=find(parent[i]);
}
void unite(int i,int j){
  parent[find(i)]=find(j);
}

vector<int>v[lim];

int n,m;

int col[lim];

int query(vector<int>tosave,int def){
  vector<int>toask(n,def);
  for(int i:tosave){
    toask[i]=-1;
  }
  // cerr<<"gotta fart : ";
  // for(int i:toask)cerr<<i<<' ';
  // cerr<<'\n';
  return ask(toask);
}

int countcomponent(vector<int>banned){
  int ihate[n]{};
  for(int j:banned){
    ihate[j]=1;
  }
  set<int>comps;
  for(int i=0;i<n;i++){
    parent[i]=i;
  }
  for(int i=0;i<n;i++){
    if(ihate[i])continue;
    for(int j:v[i]){
      if(ihate[j])continue;
      unite(i,j);
    }
  }
  for(int i=0;i<n;i++){
    comps.insert(find(i));
  }
  return comps.size();
}

int copyfrom[lim];

vector<int>find_colours(int N,vector<int>X,vector<int>Y) {
  n=N;
  for(int i=0;i<n;i++){
    col[i]=-1;
    copyfrom[i]=i;
  }
  m=X.size();
  for(int i=0;i<m;i++){
    v[X[i]].pb(Y[i]);
    v[Y[i]].pb(X[i]);
  }
  int dist[n]{};
  for(int i=0;i<n;i++){
    dist[i]=-1;
  }
  vector<int>sp[2];
  queue<int>q;
  q.push(0);
  dist[0]=0;
  while(q.size()){
    int node=q.front();
    q.pop();
    sp[dist[node]&1].pb(node);
    for(int j:v[node]){
      if(dist[j]==-1){
        dist[j]=dist[node]+1;
        q.push(j);
      }
    }
  }
  for(int x=0;x<2;x++){
    auto ogguys=sp[x];
    // cerr<<"calculating : ";
    // for(int i:ogguys)cerr<<i<<' ';
    // cerr<<'\n';
    vector<int>curguys;
    for(int i=0;i<ogguys.size();i++){
      curguys.pb(ogguys[i]);
      int res=query(curguys,n);
      // cerr<<"trying "<<ogguys[i]<<' '<<res<<'\n';
      if(res!=countcomponent(curguys)){
        // cerr<<curguys.back()<<" hela fake fr fr\n";
        curguys.pop_back();
        int l=0,r=int(curguys.size())-2,ans=r+1;
        while(l<=r){
          int mid=l+r>>1;
          vector<int>ilike;
          for(int i=0;i<=mid;i++){
            ilike.pb(curguys[i]);
          }
          ilike.pb(ogguys[i]);
          int val=query(ilike,n);
          if(val==countcomponent(ilike)){
            l=mid+1;
          }else{
            r=mid-1;
            ans=mid;
          }
        }
        // cerr<<ogguys[i]<<" stole "<<curguys[ans]<<'\n';
        copyfrom[ogguys[i]]=curguys[ans];
      }
    }
    for(int c=0;c<n;c++){
      auto guys=curguys;
      while(guys.size()){
        int res=query(guys,c);
        if(res==countcomponent(guys)){
          break;
        }
        int l=0,r=int(guys.size())-2,ans=guys.size()-1;
        while(l<=r){
          int mid=l+r>>1;
          vector<int>ilike;
          for(int j=0;j<=mid;j++){
            ilike.pb(guys[j]);
          }
          res=query(ilike,c);
          if(res==countcomponent(ilike)){
            l=mid+1;
          }else{
            r=mid-1;
            ans=mid;
          }
        }
        ans=guys[ans];
        reverse(guys.begin(),guys.end());
        while(guys.back()!=ans)guys.pop_back();
        guys.pop_back();
        col[ans]=c;
      }
      for(int i=0;i<curguys.size();i++){
        if(col[curguys[i]]!=-1){
          swap(curguys[i],curguys.back());
          curguys.pop_back();
          i--;
        }
      }
    }
  }
  vector<int>toret(n);
  for(int i=0;i<n;i++){
    toret[i]=col[copyfrom[i]];
  }
  return toret;
}

// vector<int>find_colours(int N,vector<int>X,vector<int>Y) {
  
//   std::vector<int> E(N, -1);
//   int x = perform_experiment(E);
//   std::vector<int> G(N, 0);
//   if (x == 1)
//     G[0] = 1;
//   return G;
// }

• Subtask 0: 0 / 0
• Subtask 1: 3 / 3
• Subtask 2: 7 / 7
• Subtask 3: 33 / 33
• Subtask 4: 21 / 21
• Subtask 5: 36 / 36