Submission #1223857

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223857		lfe	Cave (IOI13_cave)	C++20	0 / 100	39 ms	328 KiB

cave

#include "cave.h"
#include <vector>
#include <iostream>
using namespace std;

// tryCombination(int[])
// answer(int[])

void set_arr(int a, int b, int arr[], int x, vector<bool>& bra) {
    for (int i = a; i <= b; i++) {
        if (!bra[i]) arr[i] = x;
    }
}
void flip(int a, int b, int arr[], vector<bool>& bra) {
    for (int i = a; i <= b; i++) {
        if (!bra[i]) continue;
        else arr[i] = 1 - arr[i];
    }
}

bool prov(int i, int arr[]) {
    int f = tryCombination(arr);
    if (f == -1) return true;
    else if (f > i) return true;
    else return false;
}

void exploreCave(int N) {
    vector<bool> bra(N, false);
    vector<int> rett(N, -1);
    int spak[5000];
    set_arr(0, 4999, spak, 0, bra);
    for (int i = 0; i < N; i++) {
        int bot = 0, top = N-1;
        bool svar = prov(i, spak);
        bool svar1;
        int telling = 0;
        while (bot < top && telling < 1000) {
            int mid = bot + (top-bot)/2;
            flip(mid, top, spak, bra);
            svar1 = prov(i, spak);
            if (svar == svar1) top = mid;
            else bot = mid;
            svar = svar1;
            telling++;
        }
        if (!svar) flip(bot, top, spak, bra);
        bra[i] = true;
        rett[i] = bot;
    }

    int ut[5000];
    for (int i = 0; i < N; i++) ut[rett[i]] = i;

    answer(spak, ut);
}

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