제출 #549010

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
549010		Leo121	동굴 (IOI13_cave)	C++14	100 / 100	275 ms	496 KiB

cave

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

#define forn(i, a, b) for(int i = int(a); i <= int(b); ++ i)

using namespace std;

const int lim = 5e3;
vector<int> nores;
int n;
int posiciones[lim];
int estado[lim];

void bs(int pos){
    int li = 0, ls = n - pos - 1, mitad;
    int prueba[n];
    nores.clear();
    forn(i, 0, n - 1){
        prueba[i] = (posiciones[i] == -1) ? 0 : estado[i];
        if(posiciones[i] == -1){
            nores.push_back(i);
        }
    }
    int aux = tryCombination(prueba);
    if(pos == n - 1){
        posiciones[nores[li]] = pos;
        estado[nores[li]] = (aux == -1) ? 0 : 1;
        return;
    }
    bool saber = (aux == pos);
    while(li < ls){
        mitad = (li + ls) / 2;
        forn(i, li, ls){
            prueba[nores[i]] = (i <= mitad) ? 1 : 0;
        }
        aux = tryCombination(prueba);
        if((saber && aux != pos) || (!saber && aux == pos)){
            ls = mitad;
        }
        else{
            li = mitad + 1;
        }
    }
    posiciones[nores[li]] = pos;
    if(saber){
        estado[nores[li]] = 1;
    }
}

void exploreCave(int N) {
    n = N;
    forn(i, 0, N - 1){
        posiciones[i] = -1;
        estado[i] = 0;
    }
    forn(i, 0, N - 1){
        bs(i);
    }
    int arreestado[N];
    int arreposiciones[N];
    forn(i, 0, N - 1){
        arreestado[i] = estado[i];
        arreposiciones[i] = posiciones[i];
    }
    answer(arreestado, arreposiciones);
}

• 서브태스크 1: 12 / 12
• 서브태스크 2: 13 / 13
• 서브태스크 3: 21 / 21
• 서브태스크 4: 30 / 30
• 서브태스크 5: 24 / 24