Submission #676564

#	Time	Username	Problem	Language	Result	Execution time	Memory
676564		abcdehello	Cave (IOI13_cave)	C++17	100 / 100	1010 ms	632 KiB

cave

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

int n,s[5050],d[5050];

int bs(int cor,int cur){
	vector<int> unlinked(0);
	for (int i=0;i<n;i++) if (d[i]==-1) unlinked.push_back(i);
	int l=0,r=unlinked.size()-1;
	while (l!=r){
		int m=(l+r)/2;
		int findstate[5050];
		for (int i=0;i<n;i++){
			if (d[i]==-1) findstate[i]=cor;
			else findstate[i]=s[i];
		}
		for (int i=0;i<=m;i++) findstate[unlinked[i]]=cor^1;
		int door=tryCombination(findstate);
		if (door==-1) door=n;
		if (door<=cur) r=m;
		else l=m+1;
	}
	return unlinked[l];
}

void exploreCave(int N){
	n=N;
	for (int i=0;i<n;i++) d[i]=-1;
	for (int i=0;i<n;i++){
		int cor,findstate[5050];
		for (int j=0;j<n;j++){
			if (d[j]==-1) findstate[j]=0;
			else findstate[j]=s[j];
		}
		int door=tryCombination(findstate);
		if (door==-1) door=n;
		if (door>i) cor=0;
		else cor=1;
		int sw=bs(cor,i);
		s[sw]=cor;
		d[sw]=i;
	}
	answer(s,d);
}

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