Submission #486481

#	Time	Username	Problem	Language	Result	Execution time	Memory
486481		status_coding	Cave (IOI13_cave)	C++14	100 / 100	458 ms	452 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>

using namespace std;

int N;

bool isOpen(int id, int v[])
{
    int ans = tryCombination(v);

    if(ans == -1 || ans > id)
        return true;
    return false;
}

int findPoz(int id, int curCol, int st, int dr, int col[], int qV[])
{
    if(st == dr)
        return st;

    int mij=(st+dr)/2;

    for(int i=0;i<N;i++)
    {
        if(col[i] != -1)
            qV[i]=col[i];
        else
            qV[i]=1-curCol;
    }
    for(int i=st;i<=mij;i++)
    {
        if(col[i] != -1)
            qV[i]=col[i];
        else
            qV[i]=curCol;
    }

    if(isOpen(id, qV))
        return findPoz(id, curCol, st, mij, col, qV);
    else
        return findPoz(id, curCol, mij+1, dr, col, qV);
}

void exploreCave(int n)
{
    N=n;
    int col[n];
    int id[n];
    int qV[n];

    for(int i=0;i<n;i++)
    {
        col[i]=-1;
        id[i]=-1;
    }

    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(col[j] != -1)
                qV[j]=col[j];
            else
                qV[j]=0;
        }

        int curCol = isOpen(i, qV) ? 0 : 1;
        int curPoz = findPoz(i, curCol, 0, n-1, col, qV);

        col[curPoz] = curCol;
        id[curPoz] = i;

        /*
        cout<<'\n';
        for(int i=0;i<n;i++)
            cout<<col[i]<<' ';
        cout<<'\n';

        for(int i=0;i<n;i++)
            cout<<id[i]<<' ';
        cout<<"\n\n";
        */
    }

    answer(col, id);
}

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