Submission #383944

#	Time	Username	Problem	Language	Result	Execution time	Memory
383944		ParsaAlizadeh	Cave (IOI13_cave)	C++17	100 / 100	388 ms	880 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long       ll;
typedef pair<ll, ll>    pll;
typedef pair<int, int>  pii;

#define all(x)          x.begin(), x.end()
#define kill(x)         return cout << x << endl, 0
#define X               first
#define Y               second
#define endl            '\n'

constexpr ll pw(ll a, ll b, ll mod) {
    return (!b    ? 1 :
            b & 1 ? a * pw(a * a % mod, b / 2, mod) % mod :
                    pw(a * a % mod, b / 2, mod));
}

constexpr int N   = 5e5 + 10;

int n, S[N], D[N], mark[N];

int _tryComb() {
    /*
    cout << "try: ";
    for (int i = 0; i < n; i++) {
        cout << S[i] << ' ';
    }
    cout << endl;
    */
    int res = tryCombination(S);
    return (res == -1 ? n : res);
}

void apply(int l, int r) {
    for (int i = l; i < r; i++)
        if (!mark[i])
            S[i] ^= 1;
}

void exploreCave(int _n) {
    n = _n;
    for (int i = 0; i < n; i++) {
        int ini = _tryComb() > i;
        int L = 0, R = n;
        while (R - L > 1) {
            int mid = (L + R) >> 1;
            apply(L, mid);
            int now = _tryComb() > i;
            apply(L, mid);
            (ini ^ now ? R : L) = mid;
        }
        D[L] = i;
        S[L] = 1 ^ ini;
        mark[L] = true;
    }
    answer(S, D);
}

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