# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
249656 | muhammad_hokimiyon | 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 "cave.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define dl double long
using namespace std;
const int NN = 1e9 + 7;
const int M = 26;
const ll mod = 1e9 + 7;
const ll inf = 1e18 + 7;
const dl rf = 1e-14;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void exploreCave(int N)
{
vector < pair < int , int > > ans(N , {0 , 0});
vector < int > used(N , 0);
for( int i = 0; i < N; i++ ){
vector < int > s(N , 0);
for( int j = 0; j < N; j++ ){
if( used[j] )s[j] = ans[j].se;
}
int x = tryCombination(s);
if( x < i && x != -1 )x = 1;
else x = 0;
int l = 0 , r = N - 1;
while( l < r ){
int m = (l + r) / 2;
vector < int > qr(N , 0);
for( int j = 0; j < N; j++ ){
if( used[j] ){
qr[j] = ans[j].se;
}
}
for( int j = 0; j < m; j++ ){
if( !used[j] ){
qr[j] = x;
}
}
int xx = tryCombination(qr);
if( xx >= i )r = m;
else l = m + 1;
}
ans[l] = { i , x };
}
vector < int > S;
vector < int > D;
for( int i = 0; i < N; i++ ){
S.push_back(ans[i].se);
D.push_back(ans[i].fi);
}
answer( S , D );
}