Submission #986355

#	Time	Username	Problem	Language	Result	Execution time	Memory
986355		Pyqe	Cave (IOI13_cave)	C++17	100 / 100	558 ms	600 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>

using namespace std;

long long n;
int a[5069],sq[5069];
bitset<5069> spc;

long long qr(long long ky,long long x)
{
	long long i;
	
	for(i=0;i<n;i++)
	{
		if(sq[i]<n)
		{
			a[i]=spc[sq[i]];
		}
		else
		{
			a[i]=ky^i<=x;
		}
	}
	return tryCombination(a);
}

void exploreCave(int on)
{
	long long i,lh,rh,md,zz;
	
	n=on;
	for(i=0;i<n;i++)
	{
		sq[i]=n;
	}
	for(i=0;i<n;i++)
	{
		spc[i]=qr(1,n-1)==i;
		for(lh=0,rh=n-1;lh<=rh;)
		{
			md=(lh+rh)/2;
			if(qr(spc[i],md)==i)
			{
				zz=md;
				rh=md-1;
			}
			else
			{
				lh=md+1;
			}
		}
		sq[zz]=i;
	}
	for(i=0;i<n;i++)
	{
		a[i]=spc[sq[i]];
	}
	answer(a,sq);
}

Compilation message (stderr)

cave.cpp: In function 'long long int qr(long long int, long long int)':
cave.cpp:22:13: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
   22 |    a[i]=ky^i<=x;
      |            ~^~~
cave.cpp: In function 'void exploreCave(int)':
cave.cpp:53:9: warning: 'zz' may be used uninitialized in this function [-Wmaybe-uninitialized]
   53 |   sq[zz]=i;
      |   ~~~~~~^~

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