Submission #549001

#	Time	Username	Problem	Language	Result	Execution time	Memory
549001		Leo121	Cave (IOI13_cave)	C++14	12 / 100	274 ms	468 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(!ls){
        posiciones[pos] = nores[ls];
        estado[pos] = (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)){
            li = mitad + 1;
        }
        else{
            ls = mitad;
        }
    }
    posiciones[pos] = nores[li];
    if(saber){
        estado[pos] = 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);
}

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