Submission #648589

#	Time	Username	Problem	Language	Result	Execution time	Memory
648589		a_aguilo	Cave (IOI13_cave)	C++14	12 / 100	534 ms	440 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;
    }
    answer(setInterruptors, yourInterruptor);
}

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