Submission #239774

#	Time	Username	Problem	Language	Result	Execution time	Memory
239774		Charis02	Cave (IOI13_cave)	C++14	100 / 100	316 ms	632 KiB

cave

#include "cave.h"
#define rep(i,a,b) for(int i = a;i < b;i++)

using namespace std;

int correct[25005],porta[25005];

void solve(int low,int high,int cur)
{
    if(low == high)
    {
        correct[low] = (correct[low]+1)%2;
        porta[low] = cur;

        return;
    }

    int mid = (low + high) / 2;

    rep(i,low,mid+1)
    {
        if(porta[i] == -1)
        {
            correct[i] = (correct[i] + 1)%2;
        }
    }

    if(tryCombination(correct) != cur)
    {
        rep(i,low,mid+1)
        {
            if(porta[i] == -1)
            {
                correct[i] = (correct[i] + 1)%2;
            }
        }

        solve(low,mid,cur);
    }
    else
    {
        solve(mid+1,high,cur);
    }

    return;
}

void exploreCave(int N)
{
    rep(i,0,N)
    {
        porta[i] = -1;
    }

    rep(i,0,N)
    {
        if(tryCombination(correct) != i)
        {
            rep(j,0,N)
            {
                if(porta[j] == -1)
                {
                    correct[j] = (correct[j] + 1)%2;
                }
            }
        }

        solve(0,N-1,i);
    }

    answer(correct,porta);

    return;
}

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