Submission #261606

#	Time	Username	Problem	Language	Result	Execution time	Memory
261606		oscarsierra12	Cave (IOI13_cave)	C++14	100 / 100	956 ms	872 KiB

cave

#include "cave.h"
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <memory.h>
using namespace std ;


void exploreCave(int N) {
    int ans[N], pos[N], val[N] ;
    int cur[N] ;
    memset ( ans, -1, sizeof ans ) ;
    for ( int i = 0 ; i < N ; ++i ) {
        int good = 0 ;
        for ( int j = 0 ; j < N ; ++j ) cur[j] = (ans[j] == -1?1:ans[j]) ;
        int x = tryCombination(cur) ;
        if ( x == -1 ) x = N+5 ;
        if ( x > i ) good = 1 ;
        int lw = 0, hg = N-1 ;
        while ( lw < hg ) {
            int mid = (lw + hg) >> 1 ;
            for ( int j = 0 ; j < N ; ++j ) cur[j] = (ans[j] == -1?(j <= mid?good:1-good):ans[j]) ;
            x = tryCombination(cur) ;
            if ( x==-1 ) x = N+5 ;
            if ( x > i ) hg = mid;
            else lw = mid+1 ;
        }
        ans[lw] = good ;
        pos[lw] = i ;
    }
    answer (ans, pos) ;
}

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:25:25: warning: unused variable 'val' [-Wunused-variable]
     int ans[N], pos[N], val[N] ;
                         ^~~

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