Submission #729688

#	Time	Username	Problem	Language	Result	Execution time	Memory
729688		Jean7	Cave (IOI13_cave)	C++14	76 / 100	96 ms	436 KiB

cave

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

using namespace std ;

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

void solve2 () {
    for ( int i = 0 ; i < n ; i++ ) {
        s[i] = 0 ;
    }
    for ( int i = 0 ; i < n ; i++ ) {
        s[i] = 1 ;
        d[i] = tryCombination(s) ;
        s[i] = 0 ;
    }
    answer(s,d) ;
}

void solve1 () {
    for ( int i = 0 ; i < n ; i++ ) {
        d[i] = i ;
        s[i] = 0 ;
    }
    for ( int i = 0 ; i < n ; i++ ) {
        int x = tryCombination(s) ;
        if ( x == -1 ) {
            break ;
        }
        s[x] = 1 ;
    }
    answer(s,d) ;
}

void solve () {
    for ( int i = 0 ; i < n ; i++ ) {
        s[i] = 0 ;
    }
    if ( tryCombination(s) != -1 ) {
        solve1 () ;
    }
    else {
        solve2 () ;
    }
}

void exploreCave ( int N ) {
    n = N ;
    if ( n > 2000 ) {
        solve () ;
    }
    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: 12 / 12
• Subtask 2: 13 / 13
• Subtask 3: 21 / 21
• Subtask 4: 30 / 30
• Subtask 5: 0 / 24