Submission #842716

#	Time	Username	Problem	Language	Result	Execution time	Memory
842716		dsyz	Cave (IOI13_cave)	C++17	100 / 100	949 ms	600 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
using ll = long long;
#define MAXN (1000005)

void exploreCave(int N) {
	int pos[N];
	int doorindex[N];
	bool ignore[N];
	memset(ignore,0,sizeof(ignore));
	int switches[N];
	memset(switches,0,sizeof(switches));
	for(ll cur = 0;cur < N;cur++){
		for(ll i = 0;i < N;i++){
			if(!ignore[i]){
				switches[i] = 0;
			}
		}
		ll front = tryCombination(switches);
		ll correctpos;
		if(front == cur){ //correctpos is 1
			correctpos = 1;
			ll high = N;
			ll low = 0;
			while(high - low > 1){
				ll mid = (high + low) / 2;
				for(ll i = 0;i < N;i++){
					if(!ignore[i]){
						if(i >= mid){
							switches[i] = 1;
						}else{
							switches[i] = 0;
						}
					}
				}
				ll res = tryCombination(switches);
				if(res == -1 || res > cur){
					low = mid;
				}else{
					high = mid;
				}
			}
			pos[low] = correctpos;
			doorindex[low] = cur;
			switches[low] = correctpos;
			ignore[low] = 1;
		}else{ //correctpos is 0
			correctpos = 0;
			ll high = N;
			ll low = 0;
			while(high - low > 1){
				ll mid = (high + low) / 2;
				for(ll i = 0;i < N;i++){
					if(!ignore[i]){
						if(i >= mid){
							switches[i] = 1;
						}else{
							switches[i] = 0;
						}
					}
				}
				ll res = tryCombination(switches);
				if(res != -1 && res == cur){
					low = mid;
				}else{
					high = mid;
				}
			}
			pos[low] = correctpos;
			doorindex[low] = cur;
			switches[low] = correctpos;
			ignore[low] = 1;
		}
	}
	answer(pos,doorindex);
}

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