Submission #210624

#	Time	Username	Problem	Language	Result	Execution time	Memory
210624		peuch	Cave (IOI13_cave)	C++17	13 / 100	516 ms	512 KiB

cave

#include "cave.h"

void exploreCave(int N) {
	int D[N], T[N], S[N];
	bool type = 0;
	for(int i = 0; i < N; i++){
		D[i] = -1;
		S[i] = 0;
		T[i] = 0;
	}
    for(int cur = 0; cur < N; cur++){
    	int ini = 0, fim = N;
    	for(int i = 0; i < N; i++){
   			if(D[i] != -1) T[i] = S[i];
    		else T[i] = 1;
    	}
    	if(tryCombination(T) != cur) type = 1;
    	while(ini < fim - 1){
    		int mid = (ini + fim) >> 1;
    		for(int i = ini; i < mid; i++){
    			if(D[i] != -1) T[i] = S[i];
	    		else T[i] = type;
    		}
    		for(int i = mid; i < fim; i++){
    			if(D[i] != -1) T[i] = S[i];
	    		else T[i] = !type;
    		}
    		int last = tryCombination(T);
    		if(last == cur){
    			for(int i = ini; i < mid; i++){
    				if(D[i] != -1) T[i] = S[i];
	    			else T[i] = !type;
    			}
    			for(int i = mid; i < fim; i++){
    				if(D[i] != -1) T[i] = S[i];
	    			else T[i] = type;
    			}
    			ini = mid;
    		}
    		else fim = mid;
    	}
    	D[ini] = cur;
    	S[ini] = type;
    }
    answer(S, D);
}

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