Submission #1223989

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

cave

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

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

int spak[5000];

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

void skriv(int N) {
    for (int i = 0; i < N; i++) cout << spak[i] << " ";
    cout << "\n";
}

bool prov(int i) {
    int f = tryCombination(spak);

    if (f == -1) return true;
    else if (f > i) return true;
    else return false;
}

void exploreCave(int N) {
    vector<bool> bra(5000, false);
    vector<int> rett(5000, -1);
    set_arr(0, 4999, 0, bra);
    for (int i = 0; i < N; i++) {
        int bot = 0, top = N;
        bool svar = prov(i);

        bool svar1;
        int telling = 0;
        while (bot < top && telling < 1000) {
            int mid = bot + (top-bot)/2;
            flip(mid, top, bra);
            svar1 = prov(i);
            if (svar == svar1) top = mid;
            else bot = mid;
            svar = svar1;
            telling++;
        }
        if (!svar) flip(bot, bot+1, bra);
        rett[i] = bot;
        bra[rett[i]] = true;
        
    }

    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