Submission #672821

#	Time	Username	Problem	Language	Result	Execution time	Memory
672821		mseebacher	Cave (IOI13_cave)	C++17	12 / 100	461 ms	460 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
void exploreCave(int n){
	int pos[n];
	int switched[n];
	vector<bool> vis(n,0);
	for(int i = 0;i<n;i++){
		for(int j = 0;j<n;j++){
			if(!vis[j])
				switched[j] = 1;
		}
		int l = 0;
		int r = n-1;
		int x = tryCombination(switched);
		int mid = 0;
		bool flag = 1;
		if(x == i){
			flag = 0;
		}
		while(l<r){
			mid = (l+r) /2;
			for(int h = l;h<=mid;h++){
				if(!vis[h])
					switched[h] = flag;
			}
			for(int h = 0;h<l;h++){
				if(!vis[h])
					switched[h] = !flag;
			}
			for(int h = mid+1;h<n;h++){
				if(!vis[h])
					switched[h] = !flag;
			}
			x = tryCombination(switched);
			if(x == i)
				l = mid+1;
			else r = mid;
		}
		vis[r] = 1;
		pos[r] = i;
		switched[i] = flag; 
	}
	answer(switched,pos);
}

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