Submission #710901

#	Time	Username	Problem	Language	Result	Execution time	Memory
710901		Baytoro	Cave (IOI13_cave)	C++17	100 / 100	366 ms	672 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"
//#include "graderlib.c"
using namespace std;
int realS[5005],realD[5005],inv[5005];
int n;
/*void answer(int s[], int d[]){
	for(int i=0;i<n;i++) cout<<s[i]<<' ';//
	cout<<endl;
	for(int i=0;i<n;i++) cout<<d[i]<<' ';//
	bool ok=1;
	for(int i=0;i<n;i++){
		ok&=(s[i]==realS[i]);
		ok&=(d[i]==realD[i]);
	}
	if(ok) cout<<"Correct\n";
	else cout<<"Incorrect\n";
	exit(0);
}
int tryCombination(int s[]){
	for(int i=0;i<n;i++){
		if(s[inv[i]]!=realS[inv[i]]) return i;
	}
	return -1;
}*/
const int N=5005;
int ans[N],used[N],s[N],d[N];
void exploreCave(int N) {
    n=N;
    for(int door=0;door<n;door++){
		int t=0;
		for(int i=0;i<n;i++){
			if(!used[i])
				s[i]=0;
		}
		int id=tryCombination(s);
		if(id==door){
			t=1;
			for(int i=0;i<n;i++)
				if(!used[i]) s[i]=1;
		}
		int l=0,r=n-1;
		while(l<r){
			int md=(l+r)/2;
			for(int i=l;i<=md;i++){
				if(!used[i]){
					s[i]=!t;
				}
			}
			id=tryCombination(s);
			if(id==door){
				for(int i=l;i<=md;i++) if(!used[i]) s[i]=t;
				for(int i=md+1;i<=r;i++) if(!used[i]) s[i]=!t;
				r=md;
			}
			else{
				l=md+1;
			}
		}
		s[l]=t;
		used[l]=1;
		d[l]=door;
	}
	answer(s,d);
}

/*int main(){
	cin>>n;
	for(int i=0;i<n;i++) cin>>realS[i];
	for(int i=0;i<n;i++){
		cin>>realD[i];
		inv[realD[i]]=i;
	}
	exploreCave(n);
}*/

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