Submission #1206597

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206597		HappyCapybara	Sphinx's Riddle (IOI24_sphinx)	C++20	36 / 100	33 ms	1464 KiB

sphinx

#include "sphinx.h"
#include<bits/stdc++.h>
using namespace std;

int N;
vector<int> C, num;

void solve(int l, int r, int c, int z=-1){
  if (r < l) return;
  int p = (l % 2);
  if (r % 2 != p) r--;
  //cout << l << " " << r << " " << c << endl;
  if (l == 0){
    vector<int> v(N, N);
    v[l] = -1;
    v[l+1] = c;
    if (C[l] == -1 && perform_experiment(v) < min(N, 3)){
      C[l] = c;
      num[c]++;
    }
    solve(l+2, r, c);
    return;
  }
  if (r == N-1){
    vector<int> v(N, N);
    v[r] = -1;
    v[r-1] = c;
    if (C[r] == -1 && perform_experiment(v) < min(N, 3)){
      C[r] = c;
      num[c]++;
    }
    solve(l, r-2, c);
    return;
  }
  int x = 0;
  for (int i=l; i<=r; i++) x += (C[i] == -1);
  if (x == 0) return;
  vector<int> v(N, N);
  for (int i=l; i<=r; i+=2) v[i] = -1;
  for (int i=1-p; i<N; i+=2) v[i] = c;
  if (z == -1) z = (N-perform_experiment(v))/2;
  if (z == 0) return;
  if (z == x){
    num[c] += z;
    for (int i=l; i<=r; i+=2){
      if (C[i] == -1) C[i] = c;
    }
    return;
  }
  int exp = num[c]+z;
  int m = (l+r)/2;
  if (m % 2 != p) m--;
  solve(l, m, c);
  if (num[c] != exp) solve(m+2, r, c, exp-num[c]);
}

vector<int> find_colours(int N, vector<int> X, vector<int> Y){
  ::N = N;
  C.resize(N, -1);
  num.resize(N, 0);
  for (int i=0; i<N; i++){
    solve(0, N-1, i);
    solve(1, N, i);
  }
  return C;
}

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