Submission #1242450

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242450		mychecksedad	Sphinx's Riddle (IOI24_sphinx)	C++20	36 / 100	34 ms	444 KiB

sphinx

#include "sphinx.h"
#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define pb push_back
#define pii pair<int,int>
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define ll long long int
const int N = 250;

vi g[N];
int ask(vi E){
  return perform_experiment(E);
}

std::vector<int> find_colours(int n, std::vector<int> X, std::vector<int> Y) {
  for(int i = 0; i < n; ++i) g[i].clear();
  for(int i = 0; i < n - 1; ++i) g[X[i]].pb(Y[i]), g[Y[i]].pb(X[i]);
  vi col(n, -1);


  for(int j = 0; j < n; ++j){
    vi E(n, j);
    for(int i = 0; i < n; i += 2){
      E[i] = -1;
    }
    if(ask(E) < n){
      vi S;
      for(int i = 0; i < n; i += 2) S.pb(i);
      // that means there is someone with color j
      bool ok = true;
      int L = 0;
      while(L < int(S.size())){
        ok = false;
        int l = L, r = int(S.size()) - 1, res = int(S.size());
        while(l <= r){
          int mid = l+r>>1;
          vi EE(n, j);
          int cnt = 0, is = 0;
          for(int i = L; i <= mid; ++i) EE[S[i]] = -1, ++cnt;
          if(S[L] > 0) ++is;
          if(S[mid] < n - 1) ++is;
          if(ask(EE) < cnt * 2 - 1 + is){
            res = mid;
            r = mid - 1;
          }else{
            l = mid + 1;
          }
        }
        if(res == int(S.size())) break;
        col[S[res]] = j;
        L = res + 1;
        if(L >= int(S.size())) break;
        vi EE(n, j);
        int cnt = 0, is = 0;
        for(int i = L; i < int(S.size()); ++i) EE[S[i]] = -1, ++cnt;
        if(S[L] > 0) ++is;
        if(S.back() < n - 1) ++is;
        if(ask(EE) == cnt * 2 - 1 + is){
          break;
        }
      }
    }
  }
  for(int j = 0; j < n; ++j){
    vi E(n, j);
    for(int i = 1; i < n; i += 2){
      E[i] = -1;
    }
    if(ask(E) < n){
      vi S;
      for(int i = 1; i < n; i += 2) S.pb(i);
      // that means there is someone with color j
      bool ok = true;
      int L = 0;
      while(L < int(S.size())){
        ok = false;
        int l = L, r = int(S.size()) - 1, res = int(S.size());
        while(l <= r){
          int mid = l+r>>1;
          vi EE(n, j);
          int cnt = 0, is = 0;
          for(int i = L; i <= mid; ++i) EE[S[i]] = -1, ++cnt;
          if(S[L] > 0) ++is;
          if(S[mid] < n - 1) ++is;
          if(ask(EE) < cnt * 2 - 1 + is){
            res = mid;
            r = mid - 1;
          }else{
            l = mid + 1;
          }
        }
        if(res == int(S.size())) break;
        col[S[res]] = j;
        L = res + 1;
        if(L >= int(S.size())) break;
        vi EE(n, j);
        int cnt = 0, is = 0;
        for(int i = L; i < int(S.size()); ++i) EE[S[i]] = -1, ++cnt;
        if(S[L] > 0) ++is;
        if(S.back() < n - 1) ++is;
        if(ask(EE) == cnt * 2 - 1 + is){
          break;
        }
      }
    }
  }


  return col;
}

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