Submission #136617

#	Time	Username	Problem	Language	Result	Execution time	Memory
136617		shafinalam	Cave (IOI13_cave)	C++14	100 / 100	312 ms	640 KiB

cave

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

using namespace std;

void exploreCave(int n)
{
    int D[n];
    int S[n];
    int lock[n];

    for(int i = 0; i < n; i++)
    {
        D[i] = 0;
        S[i] = 0;
        lock[i] = 0;
    }
    if(n==1)
    {
        if(tryCombination(S)==-1) answer(S, D);
        S[0] = 1;
        answer(S, D);
    }
    for(int i = 0; i < n; i++)
    {
        int lo = 0, hi = n-1;
        int last = -1, cur = -1, first = 0;

        while(lo<hi)
        {
            if(!first)
            {
                last = tryCombination(S);
                first = 1;
            }
            else last = cur;
            int mid = (lo+hi)>>1;
            for(int r = lo; r <= mid; r++)
            {
                if(!lock[r]) S[r] = 1-S[r];
            }
            cur = tryCombination(S);
            if(cur==last || (cur!=i && last!=i)) lo = mid+1;
            else hi = mid;
        }
        if(cur==i) S[lo] = 1-S[lo];
        lock[lo] = 1;
        D[lo] = i;
    }
    answer(S, D);
}

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