Submission #99293

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
99293	2019-03-02 08:32:49	Mercenary	Cave (IOI13_cave)	C++14	100 / 100	564 ms	512 KiB

cave

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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