제출 #367645

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
367645		Pulgster	동굴 (IOI13_cave)	C++17	100 / 100	477 ms	640 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
#define imie(...) " [" << #__VA_ARGS__ ": "<< (__VA_ARGS__) << "] "
#define ed <<endl
const int op = 1;
const int cl = 0;
void exploreCave(int n) {
   	int cur[n];
   	int fixed[n];
   	int mat[n];
   	for(int i=0;i<n;i++){
   		cur[i] = fixed[i] = mat[i] = 0;
   	}
    for(int i=0;i<n;i++){
    	int temp = tryCombination(cur);
    	int st;
    	if(temp == -1 or temp > i){
    		st = op;
    	} else{
    		st = cl;
    	}
    	if(st == op){
    		int lo = 0;
    		int hi = n-1;
    		while(hi != lo){
    			int mid = lo + ((hi-lo)/2);
    			int me[n];
    			for(int j=0;j<n;j++){
    				me[j] = cur[j];
    			}
    			for(int j=lo;j<=mid;j++){
    				if(!fixed[j]){
    					me[j] = !cur[j];
    				}
    			}
    			int res = tryCombination(me);
    			if(res == i){
    				hi = mid;
    			} else{
    				lo=mid+1;
    			}
    		}
    		cur[hi]=0;
    		fixed[hi]=1;
    		mat[hi] = i;
    	} else{
    		int lo = 0;
    		int hi = n-1;
    		while(hi != lo){
    			int mid = lo + ((hi-lo)/2);
    			
    			int me[n];
    			for(int j=0;j<n;j++){
    				me[j] = cur[j];
    			}
    			for(int j=lo;j<=mid;j++){
    				if(!fixed[j]){
    					me[j] = !cur[j];
    				}
    			}

    			int res = tryCombination(me);
    			
    			if(res != i){
    				hi = mid;
    			} else{
    				lo=mid+1;
    			}
    		}
    		cur[hi]=1;
    		fixed[hi]=1;
    		mat[hi]=i;
    	}
    }
    answer(cur, mat);
}

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