제출 #537072

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
537072		fuad27	동굴 (IOI13_cave)	C++17	0 / 100	576 ms	648 KiB

cave

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

vector<bool> used;
vector<bool> numbers;
vector<int> ans1;
vector<bool> ans2;
bool check = false;

int find_kth(int k, int n, int l, int r) {
	if(l == r){
		used[l] = true;
		ans1[k] = l;
		int num[n];
		for(int i = 0;i<n;i++)num[i] = numbers[i];
		num[l] = 1;
		int comb = tryCombination(num);
		if(comb > k or comb == -1) {
			ans2[k] = 1;
		}
		else {
			ans2[k] = 0;
		}
		return l;
	}
	int mid = (l+r)/2;
	int num[n];
	for(int i = 0;i<n;i++)num[i] = numbers[i];
	for(int i = 0;i<=mid;i++) {
		if(!used[i]) {
			num[i] = !num[i];
		}
	}
	int comb = tryCombination(num);
	if((comb>k or comb == -1) and !check) {
		return find_kth(k, n, l, mid);
	}
	else if((comb>k or comb == -1) and check) {
		return find_kth(k, n, mid+1, r);
	}
	else {
		return find_kth(k, n, mid+1, r);
	}
	return l;
}


void exploreCave(int N) {
	numbers = ans2 = vector<bool>(N, 0);
	used = vector<bool> (N+1, false);
	ans1 = vector<int> (N, 0);
	for(int i = 0;i<N;i++) {
		find_kth(i,N,0,N-1);
	}
	int a1[N];
	int a2[N];
	for(int i = 0;i<N;i++) {
		a1[i] = ans1[i];
	}
	for(int i = 0;i<N;i++) {
		a2[i] = ans2[i];
	}
	answer(a2, a1);
}

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