Submission #838384

#	Time	Username	Problem	Language	Result	Execution time	Memory
838384		jasmin	Cave (IOI13_cave)	C++17	100 / 100	210 ms	468 KiB

cave

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

int ask(int m, int good, int n, vector<int>& x, int comb[], int connect[]){
    
    int ask[n];
    for(int i=0; i<n; i++){

        ask[i] = comb[i];
    }

    for(int i=0; i<=m; i++){
        ask[x[i]] = good;
    }
    for(int i=m+1; i<(int)x.size(); i++){
        ask[x[i]] = 1-good;
    }

    return tryCombination(ask);
}

void exploreCave(int N) {

    const int n=N;
    
    vector<int> x(n);
    iota(x.begin(), x.end(), 0);

    int comb[n];
    int connect[n];
    for(int i=0; i<n; i++){
        comb[i] = 0;
        connect[i] = -1;
    }

    for(int i=0; i<n; i++){

        int door = tryCombination(comb);
        assert(door==-1 || i<=door);
        
        int good;
        if(door==-1 || i<door){ //door i was open
            good = 0;
        }
        else{
            good = 1;
        }

        int l=0; int r=x.size()-1;
        int ans=0;
        while(l<=r){
            int m=l+(r-l)/2;

            int door = ask(m, good, n, x, comb, connect);
            if(door == -1 || i < door){

                ans = m;
                r = m-1;
            }
            else{
                
                l = m+1;
            }
        }

        comb[x[ans]] = good;
        connect[x[ans]] = i;
        x.erase(x.begin() + ans);

    }

    answer(comb, connect);
}

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