Submission #123718

#	Time	Username	Problem	Language	Result	Execution time	Memory
123718		MAMBA	Cave (IOI13_cave)	C++17	100 / 100	1087 ms	640 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"

using namespace std;

#define rep(i , j , k) for (int i = j; i < (int)k; i++)

int N, P[5010], Q[5010], local[5010];
inline bool ask(int lim , int tp, int door) {
	rep(i , 0 , lim) {
		if (~P[i])
			local[i] = Q[i];
		else
			local[i] = tp;
	}
	rep(i , lim , N) {
		if (~P[i])
			local[i] = Q[i];
		else 
			local[i] = tp ^ 1;
	}
	int res = tryCombination(local);
	return res == -1 || res > door;
}

void exploreCave(int N_) {
	N = N_;
	memset(P , -1, sizeof(P));
	memset(Q , 0 , sizeof(Q));
 	rep(i , 0 , N) {
		int tp = 0;
		if (!ask(N , tp , i))
			tp ^= 1;
		int lo = -1, hi = N - 1;
		while (lo != hi - 1) {
			int mid = lo + hi >> 1;
			if (ask(mid + 1, tp , i))
				hi = mid;
			else 
				lo = mid;
		}
		P[hi] = i;
		Q[hi] = tp;
	}	
	answer(Q , P);
}

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:36:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int mid = lo + hi >> 1;
              ~~~^~~~

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