Submission #55674

#	Time	Username	Problem	Language	Result	Execution time	Memory
55674		leejseo	Cave (IOI13_cave)	C++98	100 / 100	418 ms	640 KiB

cave

#include "cave.h"
#include <vector>
using namespace std;

vector<int> L;


int S[5001], D[5001];
bool DONE[5001];

int binary(int s, int e, int i, int prev){
	if (s == e) return s;
	int mid = (s+e) >> 1;
	for (int j=s; j<=mid; j++) S[L[j]] ^= 1; 
	int res = tryCombination(S);
	if ((res == i) == (prev == i)) return binary(mid+1, e, i, res);
	return binary(s, mid, i, res);
}

void exploreCave(int N) {
	for (int i=0; i<N; i++){
		L.clear();
		for (int j=0; j<N; j++) if (!DONE[j]) L.push_back(j);
		int m = L.size();
		for (int j=0; j<m; j++) S[L[j]] = 0;
		int prev = tryCombination(S);
		int res = L[binary(0, m-1, i, prev)];
		D[res] = i;
		if (tryCombination(S) == i) S[res] ^= 1;
		DONE[res] = 1;
	}	
	answer(S, D);
}

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