Submission #855992

#	Time	Username	Problem	Language	Result	Execution time	Memory
855992		Huseyn123	동굴 (IOI13_cave)	C++17	100 / 100	358 ms	684 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"
using namespace std; 
void exploreCave(int N){
	int c[N]; 
	int d[N]; 
	int res[N]; 
	int res1[N];
	int h1;
	for(int i=0;i<N;i++){
		d[i]=-1;
	}
	for(int i=0;i<N;i++){
		h1=0;
		for(int j=0;j<N;j++){
			if(d[j]==-1){
				c[j]=0;
			}
			else{
				c[j]=d[j];
			}
		}
		int h=tryCombination(c);
		if(h!=i){
			h1=1;
		}
		int l,r; 
		l=0,r=N-1; 
		while(l<r){
			int m=(l+r)/2; 
			for(int j=0;j<N;j++){
				if(d[j]==-1){
					c[j]=h1;
				}
				else{
					c[j]=d[j];
				}
			}
			for(int j=l;j<=m;j++){
				if(d[j]==-1){
					c[j]=1-h1;
				}
			}
			h=tryCombination(c); 
			if(h>i || h==-1){
				r=m;
			}
			else{
				l=m+1;
			}
		}
		res[l]=1-h1;
		res1[l]=i;
		d[l]=1-h1;
	}
	answer(res,res1);
}

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