Submission #1305904

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305904		Johan	Cave (IOI13_cave)	C++20	64 / 100	204 ms	628 KiB

cave

#include "cave.h"
#include "bits/stdc++.h"
using namespace std;
const int N = 5e3 + 5;
bool vis[N];
int f(vector < int > a){
	int n = (int)a.size();
	int s[n];
	for(int i = 0; i < n; i++)
		s[i] = a[i];
	return tryCombination(s);
}
int ok(vector < int > s, bool turn, int l, int r){
	for(int i = l; i <= r; i++){
		if(vis[i] == false)
			s[i] = turn ^ 1;
	}
	int cur = f(s);
	return (cur == -1 ? 1e9 : cur);
}
void exploreCave(int n){
	vector < int > s(n, 1);
	int x = f(s);
	bool turn = (x >= 1);
	vector < pair < int , int > > y;
	while(y.size() != n){
		for(int i = 0; i < n; i++){
			if(vis[i] == false){
				s[i] = turn;
			}
		}
		x = f(s);
		if(x == -1)x = n;
		int p = 0;
		while(p < n){
			int l = p, r = n - 1;
			int best = -1;
			while(r >= l){
				int mid = (l + r) >> 1;
				if(ok(s, turn, p, mid) < x){
					r = mid - 1;
					best = mid;
				}
				else l = mid + 1;
			}
			if(best == -1)break;
			s[best] = turn ^ 1;
			y.push_back({best, f(s)});
			vis[best] = true;
			s[best] = turn;
			p = best + 1;
		}
		turn ^= 1;
	}
	sort(y.begin(), y.end());
	int e[n], o[n], id1 = 0, id2 = 0;
	for(auto [idx, va] : y)e[id1++] = va;
	for(auto i : s)o[id2++] = i;
	answer(o, e);
}

// C:\Users\Kazim\Downloads\Desktop\cavee
// g++ cave.cpp grader.c -o main

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