Submission #729689

#	Time	Username	Problem	Language	Result	Execution time	Memory
729689		Jean7	Cave (IOI13_cave)	C++14	100 / 100	689 ms	640 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
#define mid ((l+r)>>1)

using namespace std ;

int s[5002] , cur[5002] , d[5002] ;

void exploreCave ( int n ) {
    for ( int i = 0 ; i < n ; i++ ) {
        s[i] = -1 ;
    }
    for ( int i = 0 ; i < n ; i++ ) {
        for ( int j = 0 ; j < n ; j++ ) {
            cur[j] = max ( 0 , s[j] ) ;
        }
        bool o = ( tryCombination(cur) == i ) ;
        int l = 0 , r = n ;
        while ( r - l > 1 ) {
            for ( int j = 0 ; j < n ; j++ ) {
                if ( s[j] != -1 ) {
                    cur[j] = s[j] ;
                }
                else {
                    if ( j < mid ) {
                        cur[j] = 0 ;
                    }
                    else {
                        cur[j] = 1 ;
                    }
                }
            }
            if ( tryCombination(cur) == i ) {
                if ( o ) {
                    r = mid ;
                }
                else {
                    l = mid ;
                }
            }
            else {
                if ( o ) {
                    l = mid ;
                }
                else {
                    r = mid ;
                }
            }
        }
        s[l] = o ;
        d[l] = i ;
    }
    answer(s,d) ;
}

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