Submission #411495

#	Time	Username	Problem	Language	Result	Execution time	Memory
411495		Mlxa	Cave (IOI13_cave)	C++17	51 / 100	2089 ms	460 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define mp make_pair
#define mt make_tuple
#define x first
#define y second

const int N = 5050;

int n;
int s[N];
int d[N];
mt19937 rnd;
bitset<N> can, an;

int query() {
	int t = tryCombination(s);
	return t == -1 ? n : t;
}

void exploreCave(int nn) {
	n = nn;
	fill_n(d, N, -1);
	for (int i = 0; i < n; ++i) {
		vector<int> f;
		can.reset();
		for (int j = 0; j < n; ++j) {
			if (d[j] == -1) {
				f.push_back(j);
				can.set(j);
			}
		}
		int q = query();
		while (can.count() > 8) {
			// cout << can.size() << endl;
			vector<int> vec;
			an.reset();
			for (int e : f) {
				if (rnd() % 2) {
					vec.push_back(e);
					an.set(e);
					s[e] ^= 1;
				}
			}
			int t = query();
			for (int e : vec) {
				s[e] ^= 1;
			}
			assert(q >= i && t >= i);
			if ((q == i) == (t == i)) {
				can &= ~an;
			} else {
				can &= an;
			}
		}
		for (int j = 0; j < n; ++j) {
			if (!can.test(j)) {
				continue;
			}
			s[j] ^= 1;
			int t = query();
			if ((q == i) == (t == i)) {
				continue;
			}
			d[j] = i;
			if (t == i) {
				s[j] ^= 1;
			}
			break;
		}
		assert(query() > i);
	}
	answer(s, d);
}




#ifdef LC
#include "graderlib.c"

int main() {
	N = init();
	exploreCave(N);
	printf("INCORRECT\nYour solution did not call answer().\n");
	return 0;
}
#endif

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