Submission #104081

#	Time	Username	Problem	Language	Result	Execution time	Memory
104081		Lawliet	Cave (IOI13_cave)	C++14	100 / 100	563 ms	640 KiB

cave

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

#define MAX 5010

using namespace std;

int n;

int test[MAX];
int combination[MAX];

int switch_door[MAX];
int switch_state[MAX];

bool correct[MAX];

void convert(int i, int j)
{
	for(int g = i ; g <= j ; g++) 
		if(!correct[g])
			test[g] = 1 - test[g];	
}

int bs(int cur, int k)
{
	int i = 0, j = n - 1;
		
	for(int g = 0 ; g < n ; g++)
		test[g] = (correct[g]) ? combination[g] : k;
	
	while(i < j)
	{
		int m = (i + j)/2;
		
		convert(m + 1 , j);		
				
		if(tryCombination(test) != cur) convert(m + 1 , j), j = m;	
		else convert(i , j), i = m + 1;
	}
	
	return i;
}

void exploreCave(int N)
{
	n = N;
	
	for(int g = 0 ; g < n ; g++)
	{
		int i = tryCombination(combination);
		
		int cur = (i == g) ? 1 : 0;
		
		int id = bs(g , cur);
				
		correct[id] = true;
		switch_door[id] = g;
		combination[id] = cur;
		switch_state[id] = cur;
	}
	
	answer(switch_state , switch_door);
}

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