Submission #1013058

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013058		parsadox2	Cave (IOI13_cave)	C++17	100 / 100	358 ms	700 KiB

cave

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

const int N = 5e3 + 10;

int n , key[N] , ty[N];

void Find_ty(int id)
{
	int ask[n];
	for(int i = 0 ; i < n ; i++)
		ask[i] = 0;
	for(int i = 0 ; i < id ; i++)
		ask[key[i]] = ty[i];
	int ret = tryCombination(ask);
	if(ret == id)
		ty[id] = 1;
}

bool Check(int l , int r , int id)
{
	int ask[n];
	for(int i = 0 ; i < n ; i++)
		ask[i] = (ty[id] ^ 1);
	for(int i = l ; i < r ; i++)
		ask[i] = ty[id];
	for(int i = 0 ; i < id ; i++)
		ask[key[i]] = ty[i];
	int ret = tryCombination(ask);
	return (ret != id);
}

void exploreCave(int nn)
{
	n = nn;
	for(int i = 0 ; i < n ; i++)
	{
		Find_ty(i);
		int low = 0 , high = n;
		while(high - low > 1)
		{
			int mid = (low + high) >> 1;
			if(Check(low , mid , i))
				high = mid;
			else
				low = mid;
		}
		key[i] = low;
	}
	int A[n] , B[n];
	for(int i = 0 ; i < n ; i++)
	{
		B[key[i]] = i;
		A[key[i]] = ty[i];
	}
	answer(A , B);
}

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