Submission #1099894

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099894		model_code	Sphinx's Riddle (IOI24_sphinx)	C++17	36 / 100	74 ms	424 KiB

sphinx

// correct/subtask3.cpp

#include "sphinx.h"

using namespace std;

void solve(int N, vector<int> &spies, vector<int> &ans) {
  if (spies.empty()) return;

  int n = spies.size();
  vector<int> ord(N);
  for (int f = 0; f < N; ++f) {
    ord.assign(N, f);
    for (int u : spies) ord[u] = -1;
    int cnt = (2 * n + 1 - perform_experiment(ord)) / 2;

    int lo = 0, hi = n;
    while (cnt > 0) {
      while (lo + 1 < hi) {
        int mid = (lo + hi) / 2;
        ord.assign(N, f);
        for (int i = mid; i < hi; ++i) ord[spies[i]] = -1;
        int expected = 2 * (hi - mid) + 1;
        if (perform_experiment(ord) < expected) {
          lo = mid;
        } else {
          hi = mid;
        }
      }
      ans[spies[lo]] = f;
      lo = 0, --hi;
      --cnt;
    }
  }
}

vector<int> find_colours(int N, vector<int> /*X*/, vector<int> /*Y*/) {
  vector<int> F(N, -1);
  vector<int> ord(N);
  for (int f = 0; f < N; ++f) {
    ord.assign(N, f);
    ord[0] = -1;
    if (perform_experiment(ord) == 1) {
      F[0] = f;
      break;
    }
  }
  for (int f = 0; f < N; ++f) {
    ord.assign(N, f);
    ord[N - 1] = -1;
    if (perform_experiment(ord) == 1) {
      F[N - 1] = f;
      break;
    }
  }
  vector<int> spies;
  for (int i = 1; i + 1 < N; i += 2) spies.push_back(i);
  solve(N, spies, F);

  spies.clear();
  for (int i = 2; i + 1 < N; i += 2) spies.push_back(i);
  solve(N, spies, F);

  return F;
}

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