Submission #314870

#	Time	Username	Problem	Language	Result	Execution time	Memory
314870		shafinalam	Cave (IOI13_cave)	C++14	100 / 100	380 ms	632 KiB

cave

#include "cave.h"
 
void exploreCave(int N)
{
    int S[N], D[N];
    for(int i = 0; i < N; i++)
    {
        S[i] = 0;
        D[i] = -1;
    }
    for(int i = 0; i < N; i++)
    {
        int last = tryCombination(S);
        int st = 0;
        if(last==i) st = 1;

        int lo = 0, hi = N-1, pos = -1;

        while(lo<=hi)
        {
            int mid = (lo+hi)>>1;
            for(int j = lo; j <= mid; j++) 
                if(D[j]==-1) S[j] = 1-S[j];
            int p = tryCombination(S);
            for(int j = lo; j <= mid; j++) 
                if(D[j]==-1) S[j] = 1-S[j];
            if(st)
            {
                if(p>i || p==-1) 
                {
                    pos = mid;
                    hi = mid-1;
                }
                else lo = mid+1;
            }
            else
            {
                if(p==i)
                {
                    pos = mid;
                    hi = mid-1;
                }
                else lo = mid+1;
            }
        }
        S[pos] = st;
        D[pos] = i;
    }
    answer(S, D);
}

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