Submission #1206604

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206604		HappyCapybara	Sphinx's Riddle (IOI24_sphinx)	C++20	64 / 100	41 ms	3636 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);
  int M = X.size();
  if (N <= 50){
    for (int bruh=0; bruh<2*M; bruh++){
      int i = bruh % M;
      if (C[X[i]] == -1){
        vector<int> v(N, N);
        v[X[i]] = 0;
        v[Y[i]] = 0;
        int tar = perform_experiment(v);
        for (int j=0; j<N; j++){
          v[X[i]] = -1;
          v[Y[i]] = j;
          if (perform_experiment(v) == tar){
            C[X[i]] = j;
            break;
          }
        }
      }
      swap(X[i], Y[i]);
    }
    return C;
  }
  if (M == N*(N-1)/2){
    for (int i=0; i<N; i++){
      int l = 0, r = N;
      while (l < r-1){
        int m = (l+r)/2;
        int cur = 0;
        vector<int> v(N, -1);
        for (int j=0; j<N; j++){
          if (i == j) continue;
          v[j] = cur;
          if (cur < m-1) cur++;
        }
        if (perform_experiment(v) == m) r = m;
        else l = m;
      }
      C[i] = l;
    }
    return C;
  }
  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: 7 / 7
• Subtask 3: 33 / 33
• Subtask 4: 21 / 21
• Subtask 5: 0 / 36