Submission #1194208

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194208		PlayVoltz	Cave (IOI13_cave)	C++20	100 / 100	243 ms	552 KiB

cave

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

void exploreCave(int n){
	int ans[n+5], pos[n+5], type[n+5];
	vector<int> vect(n);
	for (int i=0; i<n; ++i)ans[i]=pos[i]=-1, vect[i]=i;
	for (int p=0, c; p<n; ++p){
		bool t=0;
		for (int i=0; i<n; ++i)type[i]=(pos[i]==-1?0:pos[i]);
		c=tryCombination(type);
		if (c==p){
			for (int i=0; i<n; ++i)type[i]=(pos[i]==-1?1:pos[i]);
			c=tryCombination(type);
			t=1;
		}
		int low=-1, high=vect.size();
		while (low+1<high){
			int mid=(low+high)/2;
			for (int i=0; i<vect[mid]; ++i)type[i]=(pos[i]==-1?!t:pos[i]);
			for (int i=vect[mid]; i<n; ++i)type[i]=(pos[i]==-1?t:pos[i]);
			c=tryCombination(type);
			if (c==-1||c>p)low=mid;
			else high=mid;
		}
		pos[vect[low]]=t;
		ans[vect[low]]=p;
		vect.erase(next(vect.begin(), low));
	}
	answer(pos, ans);
}

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