| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 668445 | allin27x | 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 <vector>
#include <unordered_set>
#include <deque>
#include "cave.h"
using namespace std;
int tryCombination(int S[]);
void answer(int S[], int D[]);
void exploreCave(int N){
int doors[N]={};
int perm[N] = {};
unordered_set<int> f;
int tr[N] = {};
for (int s=0; s<N; s++){
int pos = 0;
for (int i=0; i<N; i++){
if (f.count(i)) tr[i] = perm[i]; else tr[i]=0;
}
int r = tryCombination(tr);
if (r==s) pos = 1;
if (!pos) for (int i=0; i<N; i++){
if (f.count(i)) tr[i] = perm[i]; else tr[i]=1;
}
deque<int> av;
for (int i=0; i<N; i++) if (!f.count(i)) av.push_back(i);
int a = 0, b = av.size()-1;
while (a!=b){
int m = (a+b)/2;
int q = 0;
for (auto it = av.begin(); q<=m; it++){
if (!f.count(*it)) tr[*it] = pos;
q++;
}
r = tryCombination(tr);
if (r==s) {
a = m+1;
int q = 0;
for (auto it = av.begin(); q<=m; it++){
if (!f.count(*it)) tr[*it] =! pos;
q++;
}
for (int i=0; i<=m; i++) av.pop_front();
}else {
b =m;
int q = 0;
for (auto it = av.begin(); q<=m; it++){
if (!f.count(*it)) tr[*it] = pos;
q++;
}
for (int i=b; i>m; i--) av.pop_back();
}
}
doors[a] = s;
perm[a] = pos;
f.insert(a);
tr[a] = pos;
}
answer(perm, doors);
}