제출 #553522

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
553522		Trisanu_Das	동굴 (IOI13_cave)	C++17	100 / 100	1260 ms	668 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"
using namespace std;

const int MAXN = 5010;

int isDefined[MAXN],definedState[MAXN],whichNumber[MAXN],N;
int queryArray[MAXN];

int opens_kth(int got_ans,int target){
	if(got_ans == -1) return 1;
	return got_ans > target;
}

void divide_and_conquer(int target,int left,int right,int known_color){

	if(left == right){
		isDefined[left] = 1;
		definedState[left] = known_color;
		whichNumber[left] = target;
		return;
	}

	memset(queryArray,0,sizeof(queryArray));
	int mid = (left + right)/2;
	for(int i = 0;i<N;i++){
		if(left <= i && i <= mid){
			queryArray[i] = known_color;
		}
		else{
			queryArray[i] = 1 ^ known_color;
		}
	}
	for(int i = 0;i<N;i++){
		if(isDefined[i]) queryArray[i] = definedState[i];
	}

	int ans = tryCombination(queryArray);
	if(opens_kth(ans,target)){
		divide_and_conquer(target,left,mid,known_color);
	}
	else{
		divide_and_conquer(target,mid+1,right,known_color);
	}

}

int which_color(int target){

	memset(queryArray,0,sizeof(queryArray));
	for(int i = 0;i<N;i++){
		queryArray[i] = 0;
	}
	for(int i = 0;i<N;i++){
		if(isDefined[i]) queryArray[i] = definedState[i];
	}

	int ans = tryCombination(queryArray);
	if(opens_kth(ans,target)) return 0;
	else return 1;

}

void exploreCave(int n) {
    
    N = n;

    for(int i = 0;i<N;i++){
    	int known_color = which_color(i);
    	divide_and_conquer(i,0,N-1,known_color);
    }

    answer(definedState,whichNumber);

}

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