# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
964659 | marinaluca | 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.
#include "cave.h"
#include <bits/stdc++.h>
#pragma GCC optimize ("O4")
#pragma GCC optimize ("fast-math")
#pragma GCC optimize ("unroll-loops")
using namespace std;
/**
#define int long long
#define ll long long
#define all (x) begin(x), end(x)
#define xx first
#define yy second
#define cin fin
#define cout fout
typedef db double;
typedef ldb long double;
typedef vii vector <int>;
typedef pii pair <int, int>;
typedef pai pair <double, double>;
ifstream cin ("cave.in");
ofstream cout ("cave.out");
**/
const int NMAX = 5e3;
int n;
int usa[NMAX + 1];
int sus[NMAX + 1];
void intoarce (int val){
for (int i = 0; i <= val; ++ i){
if (usa[i] == -1)
sus[i] ^= 1;
}
}
void init (){
for (int i = 0; i < n; ++ i){
usa[i] = -1;
sus[i] = 0;
}
}
bool solve (int k, int poz){
intoarce(k);
int rez = tryCombination(sus);
intoarce (k);
return rez == poz;
}
void exploreCave (int N){
n = N;
init();
for (int i = 0; i < n; ++ i){
int cur = tryCombination(sus);
if (cur == i){
intoarce (n - 1);
}
int st = 0;
int dr = n - 1;
int Answer = -1;
int mijl;
while (st <= dr){
mijl = (st + dr) >> 1;
if (solve(mijl, i)){
Answer = mijl;
dr = mijl - 1;
}
else
st = mijl + 1;
}
usa[Answer] = i;
}
answer (sus, usa);
}