Submission #72703

#	Time	Username	Problem	Language	Result	Execution time	Memory
72703		RezwanArefin01	Cave (IOI13_cave)	C++17	100 / 100	845 ms	652 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"
using namespace std; 

int get(int S[]) {
    int x = tryCombination(S);
    if(x == -1) x = 1e9; 
    return x; 
}
void exploreCave(int N) {
    int S[N], D[N]; 
    memset(S, 0, sizeof S); 
    vector<pair<int, int> > v; 
    for(int i = 0; i < N; i++) {
        int b = get(S) <= i;         
        int l = 0, r = N - 1; 
        while(l < r) {                
            int m = l + r >> 1; 
            int Q[N]; 
            memset(Q, -1, sizeof Q); 
            for(auto it : v) Q[it.first] = it.second;
            for(int i = l; i <= m; i++) 
                if(Q[i] == -1) Q[i] = b; 
            for(int i = m + 1; i <= r; i++) 
                if(Q[i] == -1) Q[i] = b ^ 1; 
            if(get(Q) > i) r = m;
            else l = m + 1; 
        } v.emplace_back(l, b); 
        S[l] = b; 
        D[l] = i; 
    } answer(S, D); 
}

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:18:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
             int m = l + r >> 1; 
                     ~~^~~

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