제출 #210626

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
210626		peuch	동굴 (IOI13_cave)	C++17	100 / 100	468 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;
        	else type = 0;
        	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: 12 / 12
• Subtask 2: 13 / 13
• Subtask 3: 21 / 21
• Subtask 4: 30 / 30
• Subtask 5: 24 / 24