Submission #166691

#	Time	Username	Problem	Language	Result	Execution time	Memory
166691		dyd	Cave (IOI13_cave)	C++14	100 / 100	444 ms	516 KiB

cave

#include<bits/stdc++.h>
#include "cave.h"
const int MAXN=5010;
int s[MAXN];
int d[MAXN];
int tryCombination(int s[]);
void answer(int s[],int d[]);
void exploreCave(int n){
	/*if(tryCombination(s)==-1){
		for(int i=0;i<n;i++){
		    s[i]=1;
		    int a=tryCombination(s);
		    d[i]=a;
		    s[i]=0;
	    }
	    answer(s,d);
	}*/
	for(int i=0;i<n;i++) d[i]=-1;
	for(int i=0;i<n;i++){
		int x;
		if(tryCombination(s)==i) x=0;
		else x=1;
		int ini=0,fim=n-1;
		while(ini!=fim){
			int i0=ini;
			int m=(ini+fim)/2;
			for(int j=ini;j<=m;j++){
				if(d[j]!=-1) continue;
				s[j]=!s[j];
			}
			if(x==0){
				if(tryCombination(s)==i) ini=m+1;
				else fim=m;
			}
			if(x==1){
				if(tryCombination(s)!=i) ini=m+1;
				else fim=m;
			}
			for(int j=i0;j<=m;j++){
				if(d[j]!=-1) continue;
				s[j]=!s[j];
		    }
	    }
	    if(x==0) s[fim]=1;
	    d[fim]=i;
	}
	answer(s,d); 
	/*for(int i=0;i<n;i++){
		d[i]=i;
		if(tryCombination(s)==i) s[i]=1;
	}
	answer(s,d);*/
}

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