Submission #166538

#	Time	Username	Problem	Language	Result	Execution time	Memory
166538		igba	Cave (IOI13_cave)	C++17	0 / 100	258 ms	516 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"
const int MAXN = 5050;
int s[MAXN], d[MAXN], aux[MAXN];

void exploreCave(int n)
{
	memset(s, -1, sizeof s);
	for(int i = 1; i <= n; ++i)    
	{
		int beg = 1, end = n, mid, x, y;
		while(beg < end)
		{
			mid = (beg + end) >> 1;
			for(int j = 1; j <= n; ++j)
				aux[j] = s[j];
			for(int j = 1; j <= mid; ++j)
				if(aux[j] == -1)
					aux[j] = 0;
			x = tryCombination(aux);
			for(int j = 1; j <= n; ++j)
				aux[j] = s[j];
			for(int j = 1; j <= mid; ++j)
				if(aux[j] == -1)
					aux[j] = 1;
			y = tryCombination(aux);
			if(x > i && y > i)
				beg = mid + 1;
			else
				end = mid;
		}
		d[i] = beg;

		for(int j = 1; j <= n; ++j)
				aux[j] = s[j];
		aux[d[i]] = 0;	
		x = tryCombination(aux);
		if(x >= i)
			s[d[i]] = 0;
		else
			s[d[i]] = 1;
	}

	answer(s, d);
}

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