제출 #1242999

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1242999		noyancanturk	스핑크스 (IOI24_sphinx)	C++20	3 / 100	39 ms	860 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];

void bs(vector<int>guys,vector<int>cols){
  if(cols.size()==1){
    for(int j:guys){
      col[j]=cols[0];
    }
    return;
  }
  vector<int>nxt;
  while(cols.size()){
    int c=cols.back();
    cols.pop_back();
    if(!cols.size()&&!nxt.size()){
      nxt.pb(c);
      continue;
    }
    vector<int>toask(n,c);
    for(int j:guys)toask[j]=-1;
    int resthink=1;
    for(int i=0;i+1<n;i++)if(toask[i]!=toask[i+1])resthink++;
    int res=ask(toask);
    if(res!=resthink){
      nxt.pb(c);
    }
  }
  if(nxt.size()==1){
    for(int j:guys){
      col[j]=nxt[0];
    }
    return;
  }
  srand(time(0));
  random_shuffle(guys.begin(),guys.end());
  vector<int>sp1,sp2;
  for(int i=0;i<guys.size()/2;i++){
    sp1.pb(guys[i]);
  }
  for(int i=guys.size()/2;i<guys.size();i++){
    sp2.pb(guys[i]);
  }
  bs(sp1,nxt),bs(sp2,nxt);
}

vector<int>find_colours(int N,vector<int>X,vector<int>Y) {
  n=N;
  vector<int>sp1,sp2;
  for(int i=0;i<n;i+=2){
    sp1.pb(i);
  }
  for(int i=1;i<n;i+=2){
    sp2.pb(i);
  }
  vector<int>c(n);
  iota(c.begin(),c.end(),0);
  bs(sp1,c),bs(sp2,c);
  return vector<int>(col,col+n);
}

// 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: 0 / 7
• Subtask 3: 0 / 33
• Subtask 4: 0 / 21
• Subtask 5: 0 / 36