Submission #420820

#	Time	Username	Problem	Language	Result	Execution time	Memory
420820		hhhhaura	Cave (IOI13_cave)	C++14	0 / 100	562 ms	424 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define rrep(i, a, b) for(int i = b; i >= a; i--)
#define all(x) x.begin(), x.end()
#define ceil(a, b) ((a + b - 1) / (b))
using namespace std;
int cur[5001], a[5001], b[5001], s[5001], d[5001], n;
void make_combination(int x, int y, bool type) {
	rep(i, 0, y) cur[x] = type;
	rep(i, y + 1, n - 1) cur[x] = !type;
	rep(i, 0, x - 1) cur[a[i]] = b[i];
	return;
}
void exploreCave(int N) {
	n = N;
	rep(i, 0, n - 1) {
		make_combination(i, n - 1, 0);
		bool type = 1; int l = -1, r = n - 1; 
		if(tryCombination(cur) > i) type = 0;
   		while(r - l > 1) {
   			int mid = (l + r) / 2;
   			make_combination(i, mid, type);
   			if(tryCombination(cur) > i) r = mid;
   			else l = mid;
   		}
   		a[i] = r, b[i] = type;
	}
	rep(i, 0, n - 1) {
		s[a[i]] = b[i];
		d[a[i]] = i;
	}
	answer(s, d);
	return;
}

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