Submission #301355

#	Time	Username	Problem	Language	Result	Execution time	Memory
301355		peti1234	Cave (IOI13_cave)	C++17	100 / 100	373 ms	616 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
const int c=5002;
int par[c], t[c];
bool v[c];
void f(int a, int b) {
    for (int i=a; i<b; i++) if (!v[i]) t[i]=1-t[i];
}
bool jo(int p) {
    int x=tryCombination(t);
    if (x==-1) x=1e9;
    return x>p;
}
void exploreCave(int n) {
    for (int i=0; i<n; i++) {
        if (!jo(i)) f(0, n);
        int lo=0, hi=n;
        while(hi-lo>1) {
            int mid=(hi+lo)/2;
            f(mid, hi);
            if (jo(i)) hi=mid;
            else lo=mid, f(mid, hi);
        }
        par[lo]=i, v[lo]=1;
    }
    answer(t, par);
}

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