Submission #164832

#	Time	Username	Problem	Language	Result	Execution time	Memory
164832		Berted	Cave (IOI13_cave)	C++14	100 / 100	1008 ms	560 KiB

cave

#include "cave.h"
 
int s[5001]={},d[5001]={},n;
int tp[5001]={};
 
inline int ck()
{
	for (int i=0;i<n;i++)
	{
		if (s[i]!=-1) {tp[i] = s[i];}
		else {tp[i] = 0;}
	}
	return tryCombination(tp);
}
 
inline int ck2(int x,int y)
{
	int lg = 0;
	for (int i=0;i<n;i++)
	{
		if (s[i]!=-1) {tp[i] = s[i];}
		else
		{
			if (lg<x) {tp[i] = y;} else {tp[i] = !y;}
			lg++;
		}
	}
	return tryCombination(tp);
}
 
inline int st(int ps)
{
	int lg = 0;
	for (int i=0;i<n;i++)
	{
		if (s[i]==-1)
		{
			lg++;
			if (lg==ps) {return i;}
		}
	}
}
 
void exploreCave(int N) {
    n = N;
    for (int i=0;i<n;i++) {s[i] = -1;d[i] = -1;}
    for (int i=0;i<n;i++)
    {
    	int fl = (ck() == i);
    	int l = 1,r = n - i;
    	while (l<r)
    	{
    		int pv = (l+r)/2;
    		if (ck2(pv,fl)==i) {l = pv+1;}
    		else {r = pv;}
    	}
    	int x = st(l);
    	s[x] = fl;d[x] = i;
    }
    answer(s,d);
}

Compilation message (stderr)

cave.cpp: In function 'int st(int)':
cave.cpp:42:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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