Submission #703552

#	Time	Username	Problem	Language	Result	Execution time	Memory
703552		mircea_007	Cave (IOI13_cave)	C++17	100 / 100	914 ms	672 KiB

cave

#include "cave.h"

#define magic_sauce inline __attribute__((always_inline))

const int MAXN = 5000;
const int UNDEF = -1;
const int INF = 1e9;

int out[MAXN];
int set[MAXN];

int q[MAXN];

int p[MAXN];

int query( int n, int q[] ){
  for( int i = 0 ; i < n ; i++ )
    out[i] = set[i] < 0 ? q[i] : set[i];

  int ret = tryCombination( out );

  return ret < 0 ? +INF : ret;
}

void exploreCave( int N ){
  int i, j, val;
  int st, dr, mij;
  
  for( i = 0 ; i < N ; i++ )
    set[i] = UNDEF;

  for( i = 0 ; i < N ; i++ ){
    for( j = 0 ; j < N ; j++ )
      q[j] = 0;

    val = (query( N, q ) == i);

    st = 0;
    dr = N;
    while( dr - st > 1 ){
      mij = (dr + st) >> 1;

      for( j = 0 ; j < mij ; j++ )
        q[j] = val;
      for( ; j < N ; j++ )
        q[j] = (val ^ 1);

      if( query( N, q ) == i )
        st = mij;
      else
        dr = mij;
    }

    p[st] = i; // the st-th switch toggles the i-th door
    set[st] = val;
  }

  answer( set, p );
}

• Subtask 1: 12 / 12
• Subtask 2: 13 / 13
• Subtask 3: 21 / 21
• Subtask 4: 30 / 30
• Subtask 5: 24 / 24