Submission #99295

#	Time	Username	Problem	Language	Result	Execution time	Memory
99295		Mercenary	Cave (IOI13_cave)	C++14	100 / 100	575 ms	592 KiB

cave

#include "cave.h"

const int maxn = 5005;

int ans[maxn];
int pos[maxn];
bool vis[maxn];

void FILL_N(int l , int r , int val)
{
    for(int i = l ; i <= r ; ++i){
        if(vis[i])continue;
        ans[i] = val;
    }
}

void exploreCave(int n) {
    for(int i = 0 ; i < n ; ++i)
    {
        FILL_N(0,n-1,0);
        bool ansi = (tryCombination(ans) == i);
        // tryCombination(ans) == i -> ith door is block -> ans for ith door is 1
        //else ans for ith door is 0
        //now we need to find which switch connects to ith door
        int l = 0 , h = n - 1;
        while(l < h)
        {
//            FILL_N(0,n-1,!ansi);
            int mid = l + h >> 1;
            FILL_N(l , mid , ansi);
            FILL_N(mid + 1 , h , !ansi);
            if(tryCombination(ans) == i){
                l = mid + 1;
            }
            else{
                h = mid;
            }
        }
//        printf("%d%d\n" , l , ansi);
        pos[l] = i;
        vis[l] = 1;
        ans[l] = ansi;
    }
    return answer(ans,pos);
}

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:29:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
             int mid = l + h >> 1;
                       ~~^~~

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