Submission #648592

#	Time	Username	Problem	Language	Result	Execution time	Memory
648592		a_aguilo	Cave (IOI13_cave)	C++14	100 / 100	887 ms	464 KiB

cave

#include "cave.h"
#include<bits/stdc++.h>

using namespace std;

int n;

void applyChanges(int combo[], int l, int r, int setInterrup, int preRequisites[]){
    for(int i = l; i <= r; ++i) combo[i] = setInterrup;
    for(int i = 0; i < n;++i){
        if(preRequisites[i] != -1) combo[i] = preRequisites[i];
    }
}

void exploreCave(int N) {
    /* ... */
    //answer(switches, correspondence)
    n = N;
    int setInterruptors[N];
    memset (setInterruptors, -1, sizeof(setInterruptors));
    int yourInterruptor[N];
    for(int door = 0; door < N; ++door){
        int lo = 0; int hi = N-1;
        int InterruptVal;
        int combo[N];
        memset (combo, 0, sizeof(combo));
        applyChanges(combo, 0, 0, 0, setInterruptors);
        int ans = tryCombination(combo);
        InterruptVal = 0;
        if(ans == -1 or ans > door) InterruptVal = 0;
        else InterruptVal = 1;
        int pos = 0;
        while(lo <= hi){
            int mid = lo + (hi - lo)/2;
            memset(combo, InterruptVal^1, sizeof(combo));
            applyChanges(combo, lo, mid, InterruptVal, setInterruptors);
            ans = tryCombination(combo);
            if(ans == -1 or ans > door){
                hi = mid-1;
                pos = mid;
            }
            else lo = mid+1;
        }
        yourInterruptor[door] = pos;
        setInterruptors[pos] = InterruptVal;
    }
    int interruptToDoor[N];
    for(int i = 0; i < N; ++i){
        interruptToDoor[yourInterruptor[i]] = i;
    }
    answer(setInterruptors, interruptToDoor);
}

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