| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1075536 | mc061 | Cave (IOI13_cave) | C++17 | 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.
#pragma once
#include <bits/stdc++.h>
using namespace std;
const int sz = 5000;
int ck[sz];
int idx_for[sz];
int ans[sz];
int st[sz];
int sta_for[sz];
int tryCombination(int S[]);
int tryC(const vector<int>& state, int cur_test, int switch_pos) {
for (int i = 0; i < sz; ++i) ck[i] = switch_pos^1;
for (int i = 0; i < cur_test; ++i) {
ck[idx_for[i]] = sta_for[i];
}
for (int i = 0; i < state.size(); ++i) {
ck[state[i]] = switch_pos;
}
return tryCombination(ck);
}
void answer(int S[], int D[]);
pair<int, int> solve(int idx, const vector<int>& candidates, int open_state) {
if (candidates.size() == 1) return {candidates.front(), open_state};
vector<int> left, right;
for (int i = 0; i < candidates.size()/2; ++i) {
left.push_back(candidates[i]);
}
for (int i = candidates.size()/2; i < candidates.size(); ++i) {
right.push_back(candidates[i]);
}
int v = tryC(left, idx, open_state);
if (v != idx) return solve(idx, left, open_state);
return solve(idx, right, open_state);
}
//return switch responsible for door idx and state
pair<int, int> get_ans(int idx, vector<int> candidates) {
int v = tryC(candidates, idx, 1);
int open_state = 0;
if (v != idx) open_state = 1;
return solve(idx, candidates, open_state);
}
void exploreCave(int N) {
vector<int> candidates;
for (int i = 0; i < N; ++i) {
candidates.push_back(i);
}
for (int i = 0; i < N; ++i) {
auto [idx, state] = get_ans(i, candidates);
// cerr << idx << "->" << i << "\n";
idx_for[i] = idx;
sta_for[i] = state;
ans[idx_for[i]] = i;
st[idx_for[i]] = state;
candidates.erase(find(candidates.begin(), candidates.end(), idx));
}
// for (int i = 0; i < N; ++i) {
// cout << ans[i] << " ";
// }
// cout << "\n";
// for (int i = 0; i < N; ++i) {
// cout << st[i] << " ";
// }
// cout << "\n";
answer(st, ans);
}