Submission #286994

#	Time	Username	Problem	Language	Result	Execution time	Memory
286994		Fasho	Cave (IOI13_cave)	C++14	0 / 100	2 ms	512 KiB

cave

#include <bits/stdc++.h>
#define NN 5005
#define ll long long int
#define fo(i,x,y)	for(int i=x;i<=y;i++)
#define fs(ar,n) fo(i,1,n) cin>>ar[i]
#define sp " "
#define fast cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false)
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define ii pair<int,int>
#define lli pair<ll,ll> 
#define fast2 freopen ("in.txt","r",stdin);freopen ("out.txt","w",stdout);
#define mod 1000000007
using namespace std;
#include "cave.h"

int ans[NN],tut[NN],n;
int tutmac[NN],flag;

bool check(int l,int r,int y)
{
	fo(i,l,r)
		tutmac[i]=flag;

	for(int i=1;i<=n;i++)
	{
		if(tut[i]!=-1)
			tutmac[i]=tut[i];
	}

	if(tryCombination(tutmac)>y)
		return 1;
	return 0;
}

void bs(ll x)
{
	int l=1,r=n;
	

	fo(i,1,n)
		tutmac[i]=0;
	fo(i,1,x-1)
		tutmac[ans[i]]=tut[i];
	ll y=tryCombination(tutmac);

	flag=0;
	if(y==x)
		flag=1;

	while(l<r)
	{
		if(l==r-1)
		{
			if(check(r,r,x))
				l=r;
			break;
		}
		int mid=(l+r)/2;
		if(check(l,mid,x))
			r=mid;
		else
			l=mid+1;

	}
	tutmac[l]=flag;
	ans[x]=l;
}

void exploreCave(int N) {
    /* ... */
    n=NN;
    memset(tut,-1,sizeof(-1));
	fo(i,1,n)
		bs(i);
	answer(tut,ans);
}

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