Submission #1099926

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099926		model_code	Sphinx's Riddle (IOI24_sphinx)	C++17	50 / 100	249 ms	1188 KiB

sphinx

// partially_correct/BM-partial.cpp

#include <set>

#include "sphinx.h"

using namespace std;

int N;
int p[250];
vector<int> edge[250];
vector<int> ord;
bool reached[250];
set<int> unchecked;
bool keep[250];

int where(int x) {
  if (p[x] < 0) return x;
  return (p[x] = where(p[x]));
}

int color(int x) { return (ord[x] >= 0 ? ord[x] : where(x)); }

void dfs(int x) {
  reached[x] = true;
  for (int i : edge[x]) {
    if (!reached[i] && color(x) == color(i)) dfs(i);
  }
}

int expected() {
  for (int i = 0; i < N; i++) reached[i] = false;

  int sum = 0;
  for (int i = 0; i < N; i++) {
    if (!reached[i]) {
      sum++;
      dfs(i);
    }
  }

  return sum;
}

vector<int> find_colours(int NN, vector<int> X, vector<int> Y) {
  N = NN;
  ord.resize(N);
  for (int i = 0; i < N; i++) p[i] = -1;

  int M = X.size();
  for (int i = 0; i < M; i++) {
    edge[Y[i]].push_back(X[i]);
    edge[X[i]].push_back(Y[i]);
  }

  for (int i = 1; i < N; i++) {
    while (true) {
      for (int j = 0; j <= i; j++) ord[j] = -1;
      for (int j = i + 1; j < N; j++) ord[j] = N;
      if (perform_experiment(ord) == expected()) break;

      unchecked.clear();
      for (int j = 0; j < i; j++) {
        if (where(j) != i) unchecked.insert(where(j));
      }

      vector<int> vec(unchecked.size());
      int pos = 0;
      for (int j : unchecked) vec[pos++] = j;

      int a = 0, b = pos - 1;
      while (a != b) {
        int half = (a + b) / 2;
        for (int j = 0; j < N; j++) keep[j] = false;
        for (int j = a; j <= half; j++) keep[vec[j]] = true;
        for (int j = 0; j < i; j++) {
          if (keep[where(j)]) {
            ord[j] = -1;
          } else {
            ord[j] = N;
          }
        }
        ord[i] = -1;
        for (int j = i + 1; j < N; j++) ord[j] = N;

        if (perform_experiment(ord) == expected()) {
          a = half + 1;
        } else {
          b = half;
        }
      }
      p[where(vec[a])] = i;
    }
  }

  vector<int> F(N);
  for (int i = 0; i < N; i++) F[i] = where(i);
  return F;
}

• Subtask 0: 0 / 0
• Subtask 1: 1.5 / 3
• Subtask 2: 3.5 / 7
• Subtask 3: 16.5 / 33
• Subtask 4: 10.5 / 21
• Subtask 5: 18 / 36