Submission #104079

#	Time	Username	Problem	Language	Result	Execution time	Memory
104079		Lawliet	동굴 (IOI13_cave)	C++14	100 / 100	631 ms	624 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];

/*int tryCombination(int s[])
{
	for(int g = 0 ; g < n ; g++) printf("%d ",s[g]);
	printf("\n");
	
	int a;
	scanf("%d",&a);
	
	return a;
}*/

int bs(int cur, int k)
{
	int i = 0, j = n - 1;
	
	//todos começam com 1 - k, tirando os corretos
	
	for(int g = 0 ; g < n ; g++)
		test[g] = (correct[g]) ? combination[g] : k;
	
	while(i < j)
	{
		int m = (i + j)/2;
		//if(i == j - 1) m = j;
		
		//printf("i = %d  j = %d  m = %d\n",i,j,m);
		
		for(int g = m + 1 ; g <= j ; g++) 
			if(!correct[g])
				test[g] = 1 - test[g];		
				
		if(tryCombination(test) != cur) 
		{
			for(int g = m + 1 ; g <= j ; g++) 
				if(!correct[g])
					test[g] = 1 - test[g];
					
			j = m;	
		}
		else
		{
			for(int g = i ; g <= j ; g++) 
				if(!correct[g])
					test[g] = 1 - test[g];
					
			i = m + 1;
		}
		
		//for(int g = 0 ; g < n ; g++) printf("%d ",test[g]);
		//printf("\n");
	}
	
	return i;
}

void exploreCave(int N)
{
	n = N;
	
	for(int g = 0 ; g < n ; g++)
	{
		int i = tryCombination(combination);//tudo com 0, menos os corretos
		
		int cur = (i == g) ? 1 : 0;
		
		int id = bs(g , cur);
		
		//printf("g = %d   bs = %d\n",g,id);
		
		correct[id] = true;
		switch_door[id] = g;
		combination[id] = cur;
		switch_state[id] = cur;
	}
	
	answer(switch_state , switch_door);
	
	//for(int g = 0 ; g < n ; g++)
		//printf("%d %d\n",switch_door[g],switch_state[g]);
}

/*int main()
{
	scanf("%d",&n);
	
	exploreCave(n);
}*/

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