제출 #703552

#제출 시각아이디문제언어결과실행 시간메모리
703552mircea_007동굴 (IOI13_cave)C++17
100 / 100
914 ms672 KiB
#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 ); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...