제출 #758633

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
758633		KN200711	동굴 (IOI13_cave)	C++14	0 / 100	477 ms	424 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);
		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: 0 / 12
• Subtask 2: 0 / 13
• Subtask 3: 0 / 21
• Subtask 4: 0 / 30
• Subtask 5: 0 / 24