Submission #758634

#	Time	Username	Problem	Language	Result	Execution time	Memory
758634		KN200711	Cave (IOI13_cave)	C++14	100 / 100	849 ms	556 KiB

cave

#include "cave.h"
# include <bits/stdc++.h>
using namespace std;

int pos[5001], fn[5001], cek[5001];

void exploreCave(int N) {
	for(int i=0;i<N;i++) pos[i] = -1;
	for(int i=0;i<N;i++) {
		// cari posisinya dimana skrg
		for(int k=0;k<N;k++) {
			if(pos[k] == -1) cek[k] = 0;
			else cek[k] = pos[k];
		}
		int v = tryCombination(cek);
		if(v == -1) v = N + 1;
		bool P;
		if(v <= i) P = 1;
		else P = 0;
	//	cout<<P<<endl;
		int ans = -1, l = 0, r = N - 1;
		while(l <= r) {
			int mid = (l + r) / 2;
			for(int d=0;d<=mid;d++) {
				if(pos[d] == -1) cek[d] = 1 - cek[d];
			}
		//	for(int k=0;k<N;k++) cout<<cek[k]<<" ";
		//	cout<<endl;
			int sv = tryCombination(cek);
			if(sv == -1) sv = N + 1;
		//	cout<<"mid : "<<mid<<" "<<sv<<endl;
			bool Q;
			if(sv <= i) {
				Q = 1;
			} else Q = 0;
			
			if(P == Q) {
				ans = mid;
				l = mid + 1;
			} else {
				r = mid - 1;
			}
			
			for(int d=0;d<=mid;d++) {
				if(pos[d] == -1) cek[d] = 1 - cek[d];
			}
		}
		ans++;
	//	cout<<i<<" "<<ans<<endl;
		pos[ans] = P;
		fn[ans] = i;
	}
	answer(pos, fn);
}

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