Submission #486454

#	Time	Username	Problem	Language	Result	Execution time	Memory
486454		glome	Cave (IOI13_cave)	C++17	100 / 100	873 ms	456 KiB

cave

#include "cave.h"
#include<bits/stdc++.h>
 
using namespace std;
void exploreCave(int N) {
	int what[N];
	int where[N];
	bool ok[N];
	for (int i = 0; i<N; i++) {
		ok[i] = 0;
		what[i] = 0;
	}
	for (int i = 0; i<N; i++) {	
		int now = 0;
		int k = tryCombination(what);
		k = (k == -1 ? N : k);
		if(k == i) {
			now = 1;
		}
		int l = 0, r = N - 1;
		int pos;
		while(l < r) {
			int l1 = l, r1 = l + (r - l) / 2;
			int l2 = l + (r - l) / 2 + 1, r2 = r;
			int temp[N];
			for (int j = 0; j<N; j++) {
				if(ok[j]) {
					temp[j] = what[j];
					continue;
				}
				if(j >= l2 && j <= r2) {
					temp[j] = now;
				}
				else {
					temp[j] = now ^ 1;
				}
			}
			int o = tryCombination(temp);
			if(o == i) {
				l = l1, r = r1;
			}
			else {
				l = l2, r = r2;
			}
		}
		pos = r;
		ok[pos] = 1;
		what[pos] = now;
		where[pos] = i;
	}
	answer(what, where);
}

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