Submission #1306810

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306810		madamadam3	Sphinx's Riddle (IOI24_sphinx)	C++20	24 / 100	40 ms	904 KiB

sphinx

#include "sphinx.h"
#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

vi find_colours(int n, vi X, vi Y) {
  vi G(n, 0);

  auto first_k_colours = [&](int target, int k) {
    if (k >= n) {
      vi e(n, n-1); e[target] = 1;
      return e;
    }

    vi e(n, n); e[target] = -1;

    int colour = 0;
    for (int i = 0; i < target && k > 0; i++) {
      e[i] = colour;
      k--; colour++;
    }

    for (int i = target + 1; i < n && k > 0; i++) {
      e[i] = colour;
      k--; colour++;
    }

    return e;
  };

  auto expected_cmps = [](vi experiment) {
    return set<int>(experiment.begin(), experiment.end()).size();
  };
 
  for (int i = 0; i < n; i++) {
    int lo = 0, hi = n;
    while (lo < hi) {
      int mid = lo + (hi - lo) / 2;
      vi e = first_k_colours(i, mid);
      int x = perform_experiment(e);

      if (x == expected_cmps(e)) {
        lo = mid + 1;
      } else {
        hi = mid;
      }
    }

    G[i] = lo - 1;
  }
  return G;
}

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