Submission #518374

#	Time	Username	Problem	Language	Result	Execution time	Memory
518374		sliviu	Cave (IOI13_cave)	C++14	0 / 100	168 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;
	//for (int i = 0; i < n; ++i)
		//cout << cur[i] << ' ';
	//cout << '\n';
	vector<int> solved(n);
	for (int i = 0; i < n; ++i) {
		int spos, dpos = 0;
		auto ok = [&](int cur[]) {
			int ok = tryCombination(cur);
			//cout << "TRYCOMB " << i << ' ' << ok << '\n';
			return !(ok > i || ok == -1);
		};
		spos = ok(cur);
		//cout << i << ' ' << spos << '\n';
		for (int j = 1; j <= N; ++j) {
			for (int t = 0; t < n; ++t)
				pos[t] = cur[t];
			//cout << "POSB CHECK : ";
			//for (int i = 0; i < n; ++i)
				//cout << pos[i] << ' ';
			//cout << '\n';
			for (int k = dpos; k < n; k += (1 << j))
				if (!solved[k])
					pos[k] = 1;
			//cout << "POSA CHECK : ";
			//for (int i = 0; i < n; ++i)
				//cout << pos[i] << ' ';
			//cout << '\n';
			dpos |= ((ok(pos) ^ spos ^ 1) << (j - 1));
		}
		for (int t = 0; t < n; ++t)
			pos[t] = cur[t];
		//cout << "DB " << dpos << '\n';
		pos[dpos] = 1;
		dpos |= ((ok(pos) ^ spos ^ 1) << N);
		//cout << "DA " << dpos << '\n';
		cur[dpos] = spos;
		d[dpos] = i;
		s[dpos] = spos;
		solved[dpos] = 1;
		//cout << "CUR CHECK : ";
		//for (int i = 0; i < n; ++i)
			//cout << cur[i] << ' ';
		//cout << '\n';
	}
	answer(s, d);
}

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