Submission #729687

#	Time	Username	Problem	Language	Result	Execution time	Memory
729687		Jean7	Cave (IOI13_cave)	C++14	51 / 100	421 ms	424 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 ;
    }
    for ( int i = 0 ; i < n ; i++ ) {
        s[i] ^= 1 ;
        d[i] = tryCombination(s) ;
        s[i] ^= 1 ;
    }
    answer(s,d) ;
}

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