Submission #400204

#	Time	Username	Problem	Language	Result	Execution time	Memory
400204		Jasiekstrz	Cave (IOI13_cave)	C++17	100 / 100	370 ms	560 KiB

cave

#include<bits/stdc++.h>
#include "cave.h"
#define fi first
#define se second
using namespace std;
const int NN=5e3;
int pos[NN+10];
int door[NN+10];
bool vis[NN+10];
void rev(int l,int r)
{
	for(int i=l;i<r;i++)
	{
		if(!vis[i])
			pos[i]=!pos[i];
	}
	return;
}
void exploreCave(int N)
{
	for(int i=0;i<N;i++)
	{
		if(tryCombination(pos)!=i)
			rev(0,N);
		int bg=0,en=N-1;
		while(bg<en)
		{
			int mid=(bg+en+1)/2;
			rev(bg,mid);
			int tmp=tryCombination(pos);
			rev(bg,mid);
			if(tmp!=i)
				en=mid-1;
			else
				bg=mid;
		}
		pos[bg]=!pos[bg];
		vis[bg]=true;
		door[bg]=i;
	}
	answer(pos,door);
	return;
}

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