Submission #676558

#	Time	Username	Problem	Language	Result	Execution time	Memory
676558		abcdehello	Cave (IOI13_cave)	C++14	0 / 100	416 ms	588 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+1)/2;
		int findstate[5050];
		for (int i=0;i<n;i++){
			if (d[i]==-1) findstate[i]=0;
			else findstate[i]=s[i];
		}
		for (int i=0;i<m;i++) findstate[unlinked[i]]=1;
		int door=tryCombination(findstate);
		if (door<cur) r=m-1;
		else l=m;
	}
	return 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>i) cor=0;
		else cor=1;
		int sw=bs(cor,i);
		d[sw]=i;
		s[sw]=cor;
	}
	answer(s,d);
}

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