| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 241182 | abacaba | Cave (IOI13_cave) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <chrono>
#include <vector>
#include <map>
#include <random>
#include <set>
#include <algorithm>
#include <math.h>
#include <cstdio>
#include <stdio.h>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <deque>
#include <cassert>
#include <stack>
#include "cave.h"
using namespace std;
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define ppb pop_back
#define emb emplace_back
#define ll long long
#define ull unsigned long long
#define cntbit(x) __builtin_popcount(x)
#define endl '\n'
#define uset unordered_set
#define umap unordered_map
#define pii pair<int, int>
#define ld long double
#define pll pair<long long, long long>
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline T range(T l, T r) {
return uniform_int_distribution<T>(l, r)(rng);
}
inline void setin(string s) {
freopen(s.c_str(), "r", stdin);
}
inline void setout(string s) {
freopen(s.c_str(), "w", stdout);
}
template <typename T> void Min(T &a, T b) {
a = min(a, b);
}
template <typename T> void Max(T &a, T b) {
a = max(a, b);
}
bool used[MAX_N];
int cur;
int correct[MAX_N], door[MAX_N];
int s[MAX_N];
int ask_full(vector <int> now, int n, int c) {
for(int i = 0; i < n; ++i)
if(used[i])
s[i] = correct[i];
for(int i : now)
s[i] = c;
return tryCombination(s);
}
void rec(vector <int> now, int n, int right_c) {
if(now.size() == 1) {
correct[now[0]] = right_c;
door[now[0]] = cur;
used[now[0]] = true;
}
else {
vector <int> temp = {};
int mid = now.size() / 2;
for(int i = 0; i < now.size(); ++i) {
if(i < mid)
temp.pb(now[i]);
else {
used[now[i]] = true;
correct[now[i]] = right_c;
}
}
int res = ask_full(temp, n, !right_c);
for(int i : now)
used[i] = false, correct[i] = -1;
if(res == -1 || res > cur) {
temp.clear();
for(int i = mid; i < now.size(); ++i)
temp.pb(now[i]);
}
rec(temp, n, right_c);
}
}
void exploreCave(int n) {
for(cur = 0; cur < n; ++cur) {
vector <int> now = {};
for(int j = 0; j < n; ++j)
if(!used[j])
now.pb(j);
int x = ask_full(now, n, 1);
rec(now, n, x == -1 || x > cur);
}
answer(correct, door);
}