Submission #1209730

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209730		trimkus	Sphinx's Riddle (IOI24_sphinx)	C++20	0 / 100	0 ms	424 KiB

sphinx

#include "sphinx.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> E;
const int MAXN = 250;
vector<vector<int>> adj(MAXN);
int expected(int N) {
  int cnt = 1;
  for (int i = 1; i < N; ++i) {
    cnt += (E[i] != E[i - 1]);
  }
  return cnt;
}

int prepare(int parity, int s, int e, int col, int N) {
  cerr << "QUERY WITH [" << s << " , " << e << "]: ";
  if (parity == (s & 1)) {
    // s--;
  }
  if (parity == (e & 1)) {
    // e += 1;
  }
  for (auto& u : E) u = N;
  for (int i = max(0, s); i <= min(N - 1, e); ++i) {
    if ((i & 1) == parity) E[i] = -1;
    else E[i] = col;
  }
  for (int i = 0; i < N; ++i) {
    cerr << E[i] << " ";
  }
  cerr << "\n";
  int empty = expected(N);
  int got = perform_experiment(E);
  cerr << "EMPTY = " << empty << " , GOT = " << got << "\n";
  return empty - got;
}

void go(int parity, int start, int end, int color, int N, vector<int>& F, int delta) {
    int nstart = start;
    int nend = end;
    if ((start % 2) != parity) nstart++;
    if ((nend % 2) != parity) nend--;
    if (nstart > nend) return;
    if (nstart == nend) {
      cerr << "FOUND COLOR = " << color << ", AT " << nstart << "!\n";
      F[nstart] = color;
      return;
    }
    int mid = (nstart + nend) / 2;
    cerr << "CHECKING NOW COLOR " << color << " , with parity = " << parity << " , at interval = [" << nstart << " , " << mid << "], with end = " << nend << "\n";
    // cerr << "INITIAL ARRAY = ";
    // for (auto& u : E) {
    //   cerr << u << " ";
    // }
    // cerr << "\n";
    int diffl = prepare(parity, nstart, mid, color, N);
    int diffr = delta - diffl;
    cerr << "initial delta = " << delta << " , got left = " << diffl << " , got right = " << diffr << "\n";
    if (diffl) go(parity, nstart, mid, color, N, F, diffl);
    if (diffr) go(parity, mid, nend, color, N, F, diffr); 
}

std::vector<int> find_colours(int N, std::vector<int> X, std::vector<int> Y) {
  int M = (int)X.size();
  for (int i = 0; i < M; ++i) {
    adj[X[i]].push_back(Y[i]);
    adj[Y[i]].push_back(X[i]);
  }
  E = vector<int>(N);
  vector<int> F(N);
  for (int par = 0; par < 2; ++par) {
    for (int i = 24; i <= 24; ++i) {
      int nstart = 0, nend = N - 1;
      if (nstart % 2 != par) nstart++;
      if (nend % 2 != par) nend--;
      int delta = prepare(par, nstart, nend, i, N);
      if (delta > 0) {
        go(par, nstart, nend, i, N, F, delta);
      }
    }
  }
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < N; ++j) {
      E[j] = i;
    }
    E[N - 2] = -1;
    if (perform_experiment(E) == 1) {
      F[N - 2] = i;
      break;
    }
  }
  return F;
}

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