Submission #800909

#	Time	Username	Problem	Language	Result	Execution time	Memory
800909		PixelCat	Cave (IOI13_cave)	C++14	100 / 100	545 ms	552 KiB

cave

#include "cave.h"

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
// #define int LL
using namespace std;
using LL = long long;
using pii = pair<int, int>;

const int MAXN = 5000;

int alive[MAXN + 10];
int state[MAXN + 10];
int pos[MAXN + 10];

int query(int n) {
    int res = tryCombination(state);
    if(res < 0) return n;
    return res;
}

void exploreCave(int n) {
    For(i, 0, n - 1) {
        alive[i] = 1;
    }
    For(i, 0, n - 1) {
        For(j, 0, n - 1) if(alive[j]) state[j] = 0;
        int flip_all = (query(n) > i);
        int hi = n - 1, lo = -1;
        while(hi - lo > 1) {
            int mi = (hi + lo) / 2;
            For(j, 0, n - 1) if(alive[j]) state[j] = flip_all ^ (j <= mi);
            if(query(n) > i) hi = mi;
            else lo = mi;
        }
        alive[hi] = 0;
        pos[hi] = i;
        state[hi] = 1 - flip_all;
    }
    answer(state, pos);
}

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