제출 #87995

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
87995		Pajaraja	동굴 (IOI13_cave)	C++17	100 / 100	1314 ms	640 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
int f[5000],n,t[5000];
bool provera(int l,int r,int k,bool c)
{
	int x[n];
	for(int i=0;i<n;i++)
	{
		if(f[i]!=-1)
		{
			x[i]=f[i];
			continue;
		}
		if(i>=l&&i<=r) x[i]=c;
		else x[i]=!c;
	}
	int a=tryCombination(x);
	if(k==a) return false;
	return true;
}
int binarna(int l,int r,int k,bool c)
{
	if(l==r) return l;
	int s=(l+r)/2;
	if(provera(l,s,k,c)) return binarna(l,s,k,c);
	return binarna(s+1,r,k,c);
}
void exploreCave(int N) 
{
	n=N;
	fill(f,f+5000,-1);
	for(int i=0;i<n;i++)
	{
		bool x=provera(0,n-1,i,1);
		int z=binarna(0,n-1,i,x);
		f[z]=x;
		t[z]=i;
	}
	int sol[n],soln[n];
	for(int i=0;i<n;i++)
	{
		sol[i]=f[i];
		soln[i]=t[i];
	}
	answer(sol,soln);
}

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