제출 #99295

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
99295		Mercenary	동굴 (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);
}

컴파일 시 표준 에러 (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