Submission #166573

#	Time	Username	Problem	Language	Result	Execution time	Memory
166573		igba	Cave (IOI13_cave)	C++17	100 / 100	1066 ms	640 KiB

cave

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

using namespace std;
const int MAXN = 5010;

void answer(int S[],int D[]);

int tryCombination(int S[]);

bool vis[MAXN];
int aux[MAXN];

int bb(int x,int y,int S[],int k,int p,int n){
	int meio = (x + y) / 2;
	
	if(x == y) return x;
	
	for(int i = 0;i < n;i++){
		if(i <= meio && vis[i] == false) aux[i] = (S[i] + 1) % 2;
		else aux[i] = S[i];
	}
	
	int h = tryCombination(aux);
	if(h == -1 || h > p) h = 1;
	else h = 0;
	
	if(h != k) return bb(x,meio,S,k,p,n);
	return bb(meio + 1,y,S,k,p,n);
}

void exploreCave(int n){
	int S[MAXN] , D[MAXN];
	
	memset(S,0,sizeof S);
	
	for(int i = 0;i < n;i++){
		int h = tryCombination(S);
		if(h == -1) h = 10000;
		
		//cout << "/ " << h << endl;
		
		int l;
		if(h > i) l = 1;
		else l = 0; 
		
		//cout << "l " << l << endl;
		
		int t = bb(0,n - 1,S,l,i,n);
		D[t] = i;
		vis[t] = true;
		
		if(l == 0) S[t] += 1 , S[t] %= 2;
	}
	
	answer(S,D);
}

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