Submission #1194694

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194694		aykhn	Sphinx's Riddle (IOI24_sphinx)	C++20	3 / 100	39 ms	436 KiB

sphinx

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

using namespace std;

const int MXN = 1000;

vector<int> ans;

void solve(int l, int r, int col, int N)
{
  if (l == r) 
  {
    ans[l] = col;
    return;
  }
  int mid = (l + r) >> 1;
  {
    vector<int> c1(N, 0), c2(N, 0);
    for (int i = 0; i < N; i++) 
    {
      if (i & 1) c1[i] = col;
      else 
      {
        if (l <= i && i <= mid) c1[i] = -1;
        else c1[i] = N;
      }
    }
    for (int i = 0; i < N; i++) 
    {
      if (!(i & 1)) c2[i] = col;
      else 
      {
        if (l <= i && i <= mid) c2[i] = -1;
        else c2[i] = N;
      }
    }
    if (perform_experiment(c1) != N || perform_experiment(c2) != N) solve(l, mid, col, N);
  }
  {
    vector<int> c1(N, 0), c2(N, 0);
    for (int i = 0; i < N; i++) 
    {
      if (i & 1) c1[i] = col;
      else 
      {
        if (mid + 1 <= i && i <= r) c1[i] = -1;
        else c1[i] = N;
      }
    }
    for (int i = 0; i < N; i++) 
    {
      if (!(i & 1)) c2[i] = col;
      else 
      {
        if (mid + 1 <= i && i <= r) c2[i] = -1;
        else c2[i] = N;
      }
    }
    if (perform_experiment(c1) != N || perform_experiment(c2) != N) solve(mid + 1, r, col, N);
  }
}

vector<int> find_colours(int N, vector<int> X, vector<int> Y) 
{
  ans = vector<int>(N);
  for (int col = 0; col < N; col++) solve(0, N - 1, col, N);
  return ans;
}

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