Submission #672832

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

cave

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

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