Submission #166558

#	Time	Username	Problem	Language	Result	Execution time	Memory
166558		igba	Cave (IOI13_cave)	C++17	100 / 100	1405 ms	608 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 = 0; i < n; ++i)    
	{
		int beg = 0, end = n - 1, mid, x, y;
		for(int j = 0; j < n; ++j)
			aux[j] = s[j];
		for(int j = 0; j < n; ++j)
			if(aux[j] == -1)
				aux[j] = 0;
		x = tryCombination(aux);
		if(x == -1)
			x = n;
		while(beg < end)
		{
			mid = (beg + end) >> 1;
			for(int j = 0; j < n; ++j)
				aux[j] = s[j];
			for(int j = beg; j <= mid; ++j)
				if(aux[j] == -1)
					aux[j] = 1;
			for(int j = 0; j < n; ++j)
				if(aux[j] == -1)
					aux[j] = 0;
			y = tryCombination(aux);
			if(y == -1)
				y = n;
			if((x > i && y > i) || (x == i && y == i))
				beg = mid + 1;
			else
				end = mid;
		}
		d[beg] = i;

		if(x == -1)
			x = n;
		if(x > i)
			s[beg] = 0;
		else
			s[beg] = 1;
	}

	answer(s, d);
}

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