제출 #65072

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
65072		nvmdava	Cave (IOI13_cave)	C++17	0 / 100	674 ms	640 KiB

cave

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

int ans[5001], door[5001], send[5001], n;

void find(int l, int r, int id, int in){
	if(l == r){
		ans[l] = in;
		door[id] = l;
		return;
	}
	int m = (l + r) >> 1;
	memset(send, -1, sizeof(send));
	for(int i = l; i <= m; i++){
		send[i] = 1;
	}
	for(int i = 0; i < m; i++){
		if(ans[i] != -1){
			send[i] = ans[i];
		} else if(send[i] == -1){
			send[i] = 0;
		}
	}
	int k = tryCombination(send);
	if(k == -1 || k > id){
		k = 1;
	} else {
		k = 0;
	}
	
	if((in ^ k )== 1){
		find(l, m, id, k);
	} else {
		find(m + 1, r, id, k ^ 1);
	}
}

void exploreCave(int N) {
	n = N;
	memset(ans, -1, sizeof(ans));
	memset(door, -1, sizeof(door));
	int k;
	for(int j = 0; j < n; j++){
		
		memset(send, -1, sizeof(send));
		for(int i = 0; i < n; i++){
			send[i] = max(send[i], ans[i]);
		}
		for(int i = 0; i < n; i++){
			if(send[i] == -1){
				send[i] = 1;
			}
		}
		k = tryCombination(send);
		if(k == -1 || k > j){
			k = 1;
		} else {
			k = 0;
		}
		find(0, n - 1, j, k);
	}
	
	answer(ans, door);
}

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