Submission #847809

#	Time	Username	Problem	Language	Result	Execution time	Memory
847809		sentheta	Cave (IOI13_cave)	C++17	100 / 100	880 ms	1072 KiB

cave

#include "cave.h"
#ifdef VANWIJ
	#include"/home/user/code/bits/stdc++.h"
	#define DBG 1
#else
	#include"bits/stdc++.h"
	#define DBG 0
#endif
using namespace std;

#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second

static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))

#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)

#define cerr if(DBG) cout
#define dbg(x) {cerr << "?" << #x << " : " << (x) << endl << flush;}

const int N = 5005;

int n;

int ansState[N], ansDoor[N];

int q[N];
int ask(){
	int ret = tryCombination(q);
	if(ret==-1) ret = n;
	return ret;
}

bool can[N];

void exploreCave(int _n){
	n = _n;
	
	rep(i,0,n){
		ansDoor[i] = -1;
	}
	
	// find switch that link to door
	rep(door,0,n){
		dbg(door);

		// correct and wrong states
		int correct, wrong;
		
		rep(i,0,n){
			can[i] = ansDoor[i]==-1;
			if(can[i]){
				q[i] = 1;
			}
		}
		
		{
			int ret = ask();
			if(ret > door){
				correct = 1; wrong = 0;
			}
			else{
				correct = 0; wrong = 1;
			}
		}
		
		while(1){
			int cnt = 0;
			rep(i,0,n){
				cnt += can[i];
			}
			if(cnt==1) break;
			
			bool flag = 0;
			rep(i,0,n) if(can[i]){
				if(flag) q[i] = correct;
				else q[i] = wrong;
				flag ^= 1;
			}
			
			int ret = ask();
			
			if(ret > door){
				rep(i,0,n) if(can[i]){
					can[i] &= q[i]==correct;
				}
			}
			else{
				rep(i,0,n) if(can[i]){
					can[i] &= q[i]==wrong;
				}
			}
		}
		
		int x = 0;
		while(!can[x]) x++;
		q[x] = correct;
		ansState[x] = correct;
		ansDoor[x] = door;
	}
	
	
	
	answer(ansState, ansDoor);
}

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