Submission #494480

#	Time	Username	Problem	Language	Result	Execution time	Memory
494480		Ronin13	Cave (IOI13_cave)	C++14	100 / 100	841 ms	460 KiB

cave

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


void exploreCave(int n) {
    int d[n];
    int s[n];
    int cur[n];
    for(int i=0;i<n;i++){
    	cur[i]=0;
    	d[i]=s[i]=-1;
	}
	for(int i=0;i<n;i++){
		int xx=tryCombination(cur);
		if(xx==-1)xx=1e9;
		int ind=0;
		if(xx==i)ind=1;
		int l=-1,r=n-1;
		int a[n];
		while(l+1<r){
			int mid=(l+r)/2;
			for(int j=0;j<n;j++)a[j]=cur[j];
			for(int j=0;j<=mid;j++){
				if(s[j]==-1)a[j]=ind;
			}
			for(int j=mid+1;j<n;j++){
				if(s[j]==-1)a[j]=1-ind;
			}
			 xx=tryCombination(a);
			 if(xx==-1)xx=1e9;
			if(xx>i)r=mid;
			else l=mid;
		}
		s[r]=ind;
		cur[r]=ind;
		d[r]=i;
	}
    answer(s,d);
}

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