Submission #1246659

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246659		CyberCow	Sphinx's Riddle (IOI24_sphinx)	C++20	10 / 100	30 ms	912 KiB

sphinx

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

vector<int> v[300];

vector<int> find_colours(int N, vector<int> X, vector<int> Y) {
  if(N <= 50)
  {
    vector<int> G(N, 0);
  vector<int> E(N, N);
  for (int i = 0; i < X.size(); i++)
  {
    v[X[i]].push_back(Y[i]);
    v[Y[i]].push_back(X[i]);
  }
  for (int i = 0; i < N; i++)
  {             
    E[i] = 0;
    E[v[i][0]] = 0;
    int x = perform_experiment(E);
    for (int j = 0; j < N; j++)
    {
      E[i] = -1;
      E[v[i][0]] = j;
      int y = perform_experiment(E);
      if(x == y)
      {
        G[i] = j;
        break;;
      }
    }
    E[i] = N;
    E[v[i][0]] = N;
  }
  return G;
  }
  vector<int> harc(N, N);
  vector<int> bi;
  for (int i = 0; i < N; i++)
  {
    harc[i] = -1;
    if(i == 0)
    bi.push_back(2);
    else
    bi.push_back(perform_experiment(harc));
  }
  int ne = 1;
  vector<int> ans;
  for (int i = 0; i < N; i++)
  {
    if(i == 0)
    ans.push_back(0);
    else
    {
      int st = 0;
      if(i == N - 1)
      {
        if(harc[i] == harc[i - 1])
          st = 1;
      }
      else
      {
        if(harc[i] != harc[i - 1])
          st = 1;
      }
      if(st == 1)
      {
        ans.push_back(ne);
        ne++;
        continue;
      }
      int l = 0, r = i - 2, anss = i - 1;
      while(l <= r)
      {
        int m = (l + r) / 2;
        vector<int> blblb(N, N);
        for (int j = 0; j <= m; j++)
        {
          blblb[j] = -1;
        }
        blblb[i] = -1;
        int x = perform_experiment(blblb);
        if(x == harc[m])
        {
          anss= m;
          r = m - 1;
        }
        else
        l = m + 1;
      }
      ans.push_back(ans[anss]);
    }
  }
  return ans;
}

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