Submission #766533

#	Time	Username	Problem	Language	Result	Execution time	Memory
766533		Sohsoh84	Cave (IOI13_cave)	C++17	0 / 100	182 ms	432 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll MAXN = 5000 + 10;

int *S, n, *comb, pans, *D;

inline int get() {
	return tryCombination(comb);
}

inline void flip(int l, int r) {
	for (int i = l; i <= r; i++)
		if (!D[i])
			comb[i] ^= 1;
}

void solve(int ind, int l, int r) {
	if (l == r) {
		D[l] = ind;
		if (pans == ind)
			comb[l] ^= 1;
		S[l] = comb[l];
		
		return;
	}

	int mid = (l + r) >> 1;
	flip(l, mid);
	int x = get();
	flip(l, mid);

	if ((pans == ind) == (x == ind)) solve(ind, mid + 1, r);
	else solve(ind, l, mid);
}

void exploreCave(int N_) {
	n = N_;
	D = new int[n];
	S = new int[n];
	comb = new int[n];	
	for (int i = 0; i < n; i++)
		D[i] = S[i] = comb[i] = 0;

	for (int i = 0; i < n; i++) {
		pans = get();
		solve(i, 0, n - 1);
	}

	answer(S, D);
}

// TODO: remove extra one

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