Submission #55673

#	Time	Username	Problem	Language	Result	Execution time	Memory
55673		leejseo	Cave (IOI13_cave)	C++98	0 / 100	137 ms	580 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: 0 / 12
• Subtask 2: 0 / 13
• Subtask 3: 0 / 21
• Subtask 4: 0 / 30
• Subtask 5: 0 / 24