Submission #288003

#	Time	Username	Problem	Language	Result	Execution time	Memory
288003		TMJN	Cave (IOI13_cave)	C++17	100 / 100	995 ms	888 KiB

cave

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


/*
int SS[5000],DD[5000],__N,RR[5000];

int tryCombination(int *P){
	cout<<'!';
	for(int i=0;i<__N;i++){
		cout<<' '<<P[i];
	}
	cout<<endl;
	
	for(int i=0;i<__N;i++){
		if(SS[RR[i]]!=P[RR[i]]){
			cout<<i<<endl;
			return i;
		}
	}
	cout<<-1<<endl;
	return -1;
}

void answer(int *SSS,int *DDD){
	for(int i=0;i<__N;i++){
		cout<<' '<<SSS[i];
	}
	cout<<endl;
	for(int i=0;i<__N;i++){
		cout<<' '<<DDD[i];
	}
	cout<<endl;
}
*/
int N,S[5000],D[5000],A[5000],T[5000];

void exploreCave(int _N) {
	N=_N;
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			A[j]=1;
		}
		for(int j=0;j<i;j++){
			A[T[j]]=S[T[j]];
		}
		int t=tryCombination(A);
		if(t==-1||i<t){
			//1:open
			int L=-1;
			int R=N-1;
			while(L+1!=R){
				int M=(L+R)/2;
				for(int j=0;j<=M;j++){
					A[j]=1;
				}
				for(int j=M+1;j<N;j++){
					A[j]=0;
				}
				for(int j=0;j<i;j++){
					A[T[j]]=S[T[j]];
				}
				int t=tryCombination(A);
				if(t==-1||i<t){
					R=M;
				}
				else{
					L=M;
				}
			}
			T[i]=R;
			S[T[i]]=1;
			D[R]=i;
		}
		else{
			//0:open
			int L=-1;
			int R=N-1;
			while(L+1!=R){
				int M=(L+R)/2;
				for(int j=0;j<=M;j++){
					A[j]=0;
				}
				for(int j=M+1;j<N;j++){
					A[j]=1;
				}
				for(int j=0;j<i;j++){
					A[T[j]]=S[T[j]];
				}
				int t=tryCombination(A);
				if(t==-1||i<t){
					R=M;
				}
				else{
					L=M;
				}
			}
			T[i]=R;
			S[T[i]]=0;
			D[R]=i;
		}
	}
	answer(S,D);
}

/*
int main(){
	cin>>__N;
	for(int i=0;i<__N;i++){
		cin>>SS[i];
	}
	for(int i=0;i<__N;i++){
		cin>>DD[i];
		RR[DD[i]]=i;
	}
	exploreCave(__N);
}
*/

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