Submission #1005183

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005183		spensa	Cave (IOI13_cave)	C++17	0 / 100	408 ms	348 KiB

cave

#include "cave.h"
#include <iostream>
#include <vector>

void exploreCave(int N) {
    int curstr[N];
    int S[N];
    int D[N];

    //they're all 0-indexed
    for(int i=0; i<N; i++) curstr[i] = 0;
    //open positions
    for(int i=0; i<N; i++) S[i] = -1;

    //cur is the door we're looking at
    for(int cur=0; cur<N; cur++){
        //construct base curstr
        for(int i=0; i<N; i++){
            curstr[i] = 0;
            if(S[i]==1) curstr[i] = 1; //let all previous doors be open
        }

        int x = tryCombination(curstr);
        int truecur;
        if(x>cur || x==-1){
            truecur = 0; //cur door is open, truecur is pos to stay open
        }
        else{
            truecur = 1;
        }

        // int fnd = 0;
        int l = 0, r = N;
        while((r-l)>1){
            //mark [l,mid]  as closed (opp of truecur)
            int mid = l + (r-l)/2;
            for(int i=l; i<mid; i++){
                curstr[i] = (truecur^1);
                if(S[i]>=0) curstr[i] = S[i]; //previous doors must stay open
            }
            //mark everything else as open (truecur)
            for(int i=0; i<l; i++){
                curstr[i] = (truecur);
            }
            for(int i=mid; i<N; i++){
                curstr[i] = (truecur);
            }

            //ask
            x = tryCombination(curstr);
            if(x==cur){
                //the cur door is in between switches l to mid
                r = mid; 
            }
            else{
                l = mid-1;
            }
        }

        //switch l connects to door cur
        S[l] = truecur;
        D[l] = cur;
    }

    answer(S, D);
    return;
}

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