Submission #1221989

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221989		hyakup	Sphinx's Riddle (IOI24_sphinx)	C++20	36 / 100	40 ms	436 KiB

sphinx

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

int bs( int n, int val, int t, vector<int> &resp ){
  int l = 0, r = n - 1;
  while( l < r ){
    int mid = ( l + r )/2;
    int aux = (( val == n - 1 ) ? val - 1 : val + 1 );
    vector<int> v(n, n);
    for( int i = 0; i < n; i++ ){
      if( i%2 != t ) v[i] = val;
      else if( i < l || mid < i ) v[i] = aux;
      else if( resp[i] != -1 ) v[i] = aux;
      else v[i] = -1;
    }

    if( perform_experiment(v) == n ) l = mid + 1;
    else r = mid;
  }
  return r;
}

void solve( int t, vector<int> &resp ){
  int n = resp.size();
  for( int i = 0; i < n; i++ ){
    while( true ){

      int aux = (( i == n - 1 ) ? i - 1 : i + 1 );
      vector<int> v(n, i);
      for( int j = 0; j < n; j++ ){
        if( j%2 == t ) v[j] = (( resp[j] == -1 ) ? -1 : aux );
      }
      if( perform_experiment(v) == n ) break;

      resp[bs( n, i, t, resp )] = i;
    }
  }
}

vector<int> find_colours(int n, vector<int> a, vector<int> b) {
  vector<int> resp(n, -1);
  solve( 0, resp );
  solve( 1, resp );
  return resp;
}

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