Submission #448282

#	Time	Username	Problem	Language	Result	Execution time	Memory
448282		M_W	Cave (IOI13_cave)	C++14	12 / 100	493 ms	528 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
int a[5050], pos[5050];
bool mark[5050];
void exploreCave(int N){
	for(int i = 0; i < N; i++){
		for(int j = 0; j < N; j++)
			if(!mark[j]) a[j] = 0;
		int zero = tryCombination(a), state;
		if(zero != i) state = 0;
		else state = 1;
		
		int l = 0, r = N-1;
		while(l < r){
			int mid = (l + r) / 2;
			for(int j = 0; j <= mid; j++)
				if(!mark[j]) a[j] = state;
			for(int j = mid + 1; j < N; j++)
				if(!mark[j]) a[j] = 1 - state;
			int ret = tryCombination(a);
			if(ret != i) r = mid;
			else l = mid + 1;
		}
		pos[i] = l;
		a[l] = state;
		mark[l] = true;
	}
	answer(a, pos);
}

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