Submission #537079

#	Time	Username	Problem	Language	Result	Execution time	Memory
537079		fuad27	Cave (IOI13_cave)	C++17	13 / 100	780 ms	2400 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;

template<typename T>
auto operator<<(ostream &os, T&v)->decltype(v.begin(), os){
	os << "[";
	int f = 0;
	for(auto i:v) {
		if(f++)os << ", ";
		os << i;
	}
	os << "]";
	return os;
}
template<typename F, typename S>
ostream& operator<<(ostream &os, pair<F, S> const &p) {
	return os << "(" << p.first << ", " << p.second << ")";
}
ostream& operator<<(ostream &os, string s) {
	for(char i:s){
		os << i;
	}
	return os;
}
void debug(){}
template<typename T, typename... V>
void debug(T t, V... v) {
	cerr << t;
	if(sizeof...(v)) {
		cerr << ", "; debug(v...);
	}
}
#ifdef LOCAL
#define dbg(x...) cerr << "[" << #x << "]: " << "["; debug(x); cerr << "]\n";
#else
#define dbg(x...)
#endif




vector<int> used;
vector<int> numbers;
vector<int> ans1;
vector<int> ans2;
bool check = false;

void find_kth(int k, int n, int l, int r) {
	dbg(k, l, r, numbers);
	if(l == r) {
		dbg(l, k);
		ans1[l] = k;
		used[l] = true;
		numbers[l] = 0;
	}
	else {
		int num[n];
		for(int i = 0;i<n;i++) {
			if(used[i])num[i] = 0;
			else num[i] = 1;
		}
		int mid = (l+r)/2;
		for(int i = l;i<=mid;i++) {
			num[i] = 0;
		}
		vector<int> tmp(n, 0);
		for(int i = 0;i<n;i++)tmp[i] = num[i];
		dbg(tmp, tryCombination(num));
		int t = tryCombination(num);
		if(t > k or t == -1) {
			find_kth(k,n,l,mid);
		}
		else {
			find_kth(k, n, mid+1, r);
		}
	}
}


void exploreCave(int N) {
	int a1[N], a2[N];
	numbers = used = ans1 = ans2 = vector<int> (N, 0);
	for(int i = 0;i<N;i++)numbers[i] = 1;
	for(int i = 0;i<N;i++) {
		find_kth(i, N, 0, N-1);
	}
	for(int i = 0;i<N;i++) {
		a1[i] = ans1[i];
		a2[i] = 0;
	}
	answer(a2, a1);
	
}

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