Submission #421619

#	Time	Username	Problem	Language	Result	Execution time	Memory
421619		hhhhaura	Cave (IOI13_cave)	C++14	51 / 100	823 ms	440 KiB

cave

#include "cave.h"
#include <cassert>
#include <cstring>
#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[i] = type;
	rep(i, y + 1, n - 1) cur[i] = !type;
	rep(i, 0, x - 1) cur[a[i]] = b[i];
	return;
}
void exploreCave(int N) {
	n = N;
	memset(cur, 0, sizeof(cur));
	memset(a, 0, sizeof(a));
	memset(b, 0, sizeof(b));
	memset(s, 0, sizeof(s));
	memset(d, 0, sizeof(d));
	rep(i, 0, n - 1) {
		make_combination(i, n - 1, 0);
		bool type = 1; int l = -1, r = n - 1; 
		int xx = tryCombination(cur);
		if(tryCombination(cur) != i) type = 0;
   		while(r - l > 1) {
   			int mid = (l + r) / 2;
   			make_combination(i, mid, type);
   			int ans = tryCombination(cur);
   			if(ans != 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;
}

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:26:7: warning: unused variable 'xx' [-Wunused-variable]
   26 |   int xx = tryCombination(cur);
      |       ^~

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