Submission #1329749

#	Time	Username	Problem	Language	Result	Execution time	Memory
1329749		Balsa	Cave (IOI13_cave)	C++20	100 / 100	149 ms	504 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>

using namespace std;

int *S, *D;
int n;

void flip(int l, int r) {
    for (int i = l; i <= r; i++) {
        if (D[i] != -1) continue;
        S[i] = !S[i];
    }
}

void solve(int ind) {
    if (tryCombination(S) == ind) flip(0, n-1);

    int l = 0, r = n-1;
    while (r != l) {
        int m = (l+r)/2;
        
        flip(l, m);
        if (tryCombination(S) == ind) r = m;
        else l = m+1;
        flip(l, m);
    }

    D[r] = ind;
}

void exploreCave(int N) {
    n = N;
    S = new int[n];
    D = new int[n];
    for (int i = 0; i < n; i++) D[i] = -1;
    
    for (int i = 0; i < n; i++) {
        solve(i);
    }

    answer(S, D);
}

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