Submission #738657

#	Time	Username	Problem	Language	Result	Execution time	Memory
738657		BidoTeima	Cave (IOI13_cave)	C++17	100 / 100	790 ms	972 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
int n;
int pos[5000];
int door[5000];
int dnc(int l, int r, bool b, int target){
    if(l == r)
        return l;
    int mid = (l + r) >> 1;
    // first check if it's in [l, mid]
    int s[n];
    for(int i = 0; i < n; i++){
        if(pos[i] != -1){
            s[i] = pos[i];
        }
        else if(l <= i && i <= mid){
            s[i] = b;
        }
        else{
            s[i] = !b;
        }
    }
    int res = tryCombination(s);
    if(res <= target && res != -1){
        return dnc(mid + 1, r, b, target);
    }
    return dnc(l, mid, b, target);
}
void exploreCave(int N) {
    n = N;
    memset(pos, -1, sizeof(pos));
    for(int i = 0; i < n; i++){
        int s[n];
        for(int j = 0; j < n; j++){
            if(pos[j] != -1)s[j] = pos[j];
            else s[j] = 0;
        }
        int res = tryCombination(s);
        bool b = 0;
        if(res <= i && res != -1){
            b = 1;
        }
        int sw = dnc(0, n-1, b, i);
        pos[sw] = b;
        door[sw] = i;
    }
    answer(pos, door);
}

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