Submission #784720

#	Time	Username	Problem	Language	Result	Execution time	Memory
784720		angels	Cave (IOI13_cave)	C++17	100 / 100	211 ms	544 KiB

cave

/******************************************************************************

                              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;
    memset(R, 0, sizeof(R));
    for(int i=0; i<n; i++)
    {
        int x=tryCombination(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(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(R, D);
}

• Subtask 1: 12 / 12
• Subtask 2: 13 / 13
• Subtask 3: 21 / 21
• Subtask 4: 30 / 30
• Subtask 5: 24 / 24