Submission #764872

#	Time	Username	Problem	Language	Result	Execution time	Memory
764872		NothingXD	Cave (IOI13_cave)	C++17	100 / 100	142 ms	496 KiB

cave

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

using namespace std;

void debug_out(){cerr << endl;}

template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cout << H << ' ';
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 5e3 + 10;

int n, s[maxn], a[maxn];
vector<int> idx;

void debugarr(int a[]){
	cerr << "arr: ";
	for (int i = 0; i < n; i++) cerr << a[i] << ' ';
	cerr << endl;
}

void exploreCave(int N) {
	n = N;
	for (int i = 0; i < n; i++) idx.push_back(i);
    for (int i = 0; i < n; i++){
		for (auto x: idx){
			s[x] = 0;
		}
		int tmp = tryCombination(s);
		if (tmp == -1 || tmp > i){
			int l = -1, r = idx.size() - 1;
			s[idx[0]] = 1;
			while(l + 1 < r){
				int mid = (l + r) >> 1;
				for (int i = l+1; i <= mid; i++){
					s[idx[i]] = 1;
				}
				int tmp = tryCombination(s);
				if (tmp == -1 || tmp > i) l = mid;
				else{
					for (int i = l+1; i <= mid; i++) s[idx[i]] = 0;
					r = mid;
				}
			}
			s[idx[r]] = 0;
			a[idx[r]] = i;
			idx.erase(idx.begin()+r);
		}
		else{
			int l = -1, r = idx.size() - 1;
			while(l + 1 < r){
				int mid = (l + r) >> 1;
				for (int i = l+1; i <= mid; i++){
					s[idx[i]] = 1;
				}
				int tmp = tryCombination(s);
				if (tmp == -1 || tmp > i){
					for (int i = l+1; i <= mid; i++) s[idx[i]] = 0;
					r = mid;
				}
				else{
					l = mid;
				}
			}
			s[idx[r]] = 1;
			a[idx[r]] = i;
			idx.erase(idx.begin()+r);
		}
	}
	answer(s, a);
}

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