Submission #518376

#	Time	Username	Problem	Language	Result	Execution time	Memory
518376		sliviu	Cave (IOI13_cave)	C++14	100 / 100	271 ms	460 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"
 
using namespace std;
 
 
void exploreCave(int n) {
	int* s = new int[n], * d = new int[n], * cur = new int[n], * pos = new int[n], N = 31 - __builtin_clz(n);
	for (int i = 0; i < n; ++i)
		cur[i] = s[i] = d[i] = pos[i] = 0;
	vector<int> solved(n);
	for (int i = 0; i < n; ++i) {
		int spos, dpos = 0;
		auto ok = [&](int cur[]) {
			int ok = tryCombination(cur);
			return !(ok > i || ok == -1);
		};
		spos = ok(cur);
		for (int j = 1; j <= N; ++j) {
			for (int t = 0; t < n; ++t)
				pos[t] = cur[t];
			for (int k = dpos; k < n; k += (1 << j))
				if (!solved[k])
					pos[k] = 1;
			dpos |= ((ok(pos) ^ spos ^ 1) << (j - 1));
		}
		if (!solved[dpos]) {
          	for (int t = 0; t < n; ++t)
				pos[t] = cur[t];
			pos[dpos] = 1;
			dpos |= ((ok(pos) ^ spos ^ 1) << N);
		}
		else
			dpos |= 1 << N;
		cur[dpos] = s[dpos] = spos;
		d[dpos] = i;
		solved[dpos] = 1;
	}
	answer(s, d);
}

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