Submission #941978

#	Time	Username	Problem	Language	Result	Execution time	Memory
941978		4QT0R	Cave (IOI13_cave)	C++17	100 / 100	534 ms	604 KiB

cave

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

void exploreCave(int n){
	int cor[n];
	fill(cor,cor+n,-1);
	int pos[n];
	fill(pos,pos+n,-1);
	int S[n];
	int kolor,odp,l,p,md,cur=0;
	for (int i = 0; i<n; i++){
		for (int j = 0; j<n; j++){
			if (cor[j]>=0)S[j]=cor[j];
			else S[j]=0;
		}
		odp=tryCombination(S);
		if (odp==-1 || odp>i)kolor=0;
		else kolor=1;

		l=1,p=n-i;
		while(l<p){
			md=(l+p)/2;
			cur=0;
			for (int j = 0; j<n; j++){
				if (cor[j]>=0)S[j]=cor[j];
				else if (cur++<md)S[j]=kolor;
				else S[j]=kolor^1;
			}
			odp=tryCombination(S);
			if (odp==-1 || odp>i)p=md;
			else l=md+1;
		}
		cur=0;
		for (int j = 0; j<n; j++){
			if (cor[j]<0 && ++cur==l)odp=j;
		}
		cor[odp]=kolor;
		pos[odp]=i;
	}
	answer(cor,pos);
}

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