Submission #107236

#	Time	Username	Problem	Language	Result	Execution time	Memory
107236		degelo	Cave (IOI13_cave)	C++17	100 / 100	477 ms	640 KiB

cave

#include<bits/stdc++.h>
#define maxn 5010
#include"cave.h"
using namespace std;
int s[maxn],d[maxn],t[maxn],N;
void setar(int ini,int fim,int v[],int val){
	for(int i=ini;i<=fim;i++){
		if(s[i]==1-val) continue;	
		v[i]=val;
	}
}
/*int tryCombination(int v[]){
	for(int i=0;i<N;i++)	printf("%d ",v[i]);
	printf("\n");
	int a;
	scanf("%d",&a);
	return a;
}*/
void exploreCave(int N){
	setar(0,N-1,s,2);
	for(int i=0;i<N;i++){
		int ini=0,fim=N-1;
		setar(ini,fim,t,0);
		int t1=tryCombination(t);
		int r;
		if(t1==i) r=1;
		else r=0;
		while(ini<fim){
			int m=(ini+fim)/2;
			setar(ini,m,t,r);
			setar(m+1,fim,t,1-r);
			int t2=tryCombination(t);
			if(t2==i){
				ini=m+1;
			}
			else{
				fim=m;
			}
		}
		d[ini]=i;
		s[ini]=r;
		//printf("%d %d\n",s[ini],d[ini]);
		t[ini]=r;
	}
	answer(s,d);
}
/*int main (){
	scanf("%d",&N);
	exploreCave(N);
	for(int i=0;i<N;i++)	printf("%d ",s[i]);
	printf("\n");
	for(int i=0;i<N;i++)	printf("%d ",d[i]);
	printf("\n");
}*/

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