제출 #1223854

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1223854		lfe	동굴 (IOI13_cave)	C++20	0 / 100	105 ms	532 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;
        while (bot < top) {
            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;
        }
        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