제출 #1217865

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1217865		lukasuliashvili	동굴 (IOI13_cave)	C++20	0 / 100	238 ms	548 KiB

cave

#include "cave.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a; i<b; i++)
void exploreCave(int N){
	int N1=2*1e6+5;
	int fix[N],ans[N],s[N],ans2[N];
	rep(i,0,N){fix[i]=-1;ans[i]=-1;}
	// ans[j] --> j chamrtvelistvis romeli karia
	// fix[i] i karistvis 1 ia tu -1 
	for(int i=0; i<N; i++){
		rep(j,0,N){
			if(ans[j]!=-1){
				s[j]=fix[ans[j]];
			}
			else{
				s[j]=0;
			}
		}
		
		int last=tryCombination(s);
		if( last<=i and last!=-1){
			fix[i]=1;
		}
		else{
			fix[i]=0;
		}
		int l=0;
		int r=N-1;
		while(l<=r){
			if(l==r){
				ans[l]=i;
				break;
			}
			int mid=(l+r)/2;
			rep(j,0,l){
				if(ans[j]!=-1){
					s[j]=fix[ans[j]];
				}
				else{
					s[j]=(fix[i]^1);
				}
			}
			rep(j,l,mid+1){
				if(ans[j]!=-1){
					s[j]=fix[ans[j]];
				}
				else{
					s[j]=fix[i];
				}
			}
			rep(j,mid+1,N){
				if(ans[j]!=-1){
					s[j]=fix[ans[j]];
				}
				else{
					s[j]=(fix[i]^1);
				}
			}
			tryCombination(s);
			cin>>last;
			if(last<=i and last!=-1){
				l=mid+1;
			}
			else{
				r=mid;
			}
		}
	}
	
	rep(i,0,N){
		ans2[i]=fix[ans[i]];
	}
	answer(ans2,ans);
	// ans2 ans 
}

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