| # | Time | Username | Problem | Language | Result | Execution time | Memory | 
|---|---|---|---|---|---|---|---|
| 784717 | angels | 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.
/******************************************************************************
                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.
*******************************************************************************/
#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
bool visited[5001];
int R[5001], D[5001];
void change(int start, int end)
{
    for(int i=start; i<=end; i++)
    {
        if(!visited[i])
        {
            if(R[i]==0)
                R[i]=1;
            else
                R[i]=0;
        }
    }
}
void exploreCave(int N)
{
    int n=N;
    for(int i=0; i<n; i++)
    {
        int x=tryCombination(n, R);
        int kiki, kiki1;
        if(x>i || x==-1)
            kiki=0;
        else 
            kiki=1;
        int start=0, end=n-1;
        while(start<end)
        {
            int mid=(start+end)/2;
            change(start, mid);
            x=tryCombination(n, R);
            if(x>i || x==-1)
                kiki1=0;
            else
                kiki1=1;
            change(start, mid);
            if(kiki==kiki1)
                start=mid+1;
            else
                end=mid;
        }
        R[start]=kiki;
        D[start]=i;
        visited[start]=true;
    }
    answer(N, R, D);
}
