Submission #1289931

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289931		ChuanChen	Cave (IOI13_cave)	C++20	0 / 100	266 ms	596 KiB

cave

#include "cave.h"
#include<bits/stdc++.h>
using namespace std;

int n;
vector<int> S, D; //S: correct position, D[i]: door connected by switch i
void _answer(vector<int> S, vector<int> D){
    int s[n], d[n];
    for(int i = 0; i < S.size(); i++) s[i] = S[i];
    for(int i = 0; i < D.size(); i++) d[i] = D[i];
    answer(s, d);
}
int _tryCombination(vector<int> S){
    int s[S.size()];
    for(int i = 0; i < S.size(); i++) s[i] = S[i];
    return tryCombination(s);
}

//encontra primeiro switch que muda porta e seu estado
void bsearch(int porta){
    //abre todas porta conhecidos,
    vector<int> guess = S, unknown;
    int verdic;

    for(int i = 0; i < n; i++){
        if(guess[i] == -1){
            guess[i] = 0;
            unknown.push_back(i);
        }
    }
    // 1 query para saber se switch deve ser aberto ou n
    verdic = _tryCombination(guess);
    // 13 query para saber onde esta esse switch
    if(verdic > porta){
        //se der true, nossa porta fica aberta com 0
        //busca binaria no unknown pra encontrar primeiro que der false;
        //000000000001111111111111
        //TTTTTTFFFFFFFFFFFFFFFFFF
        //esse ^ daqui eh nosso switch
        int l = 0, r = unknown.size()-1;
        while(l < r){
            int m = (l+r)/2;
            for(int i = 0; i <= m; i++) guess[unknown[i]] = 0;
            for(int i = m+1; i < unknown.size(); i++) guess[unknown[i]] = 1;
            verdic = _tryCombination(guess);
            if(verdic > porta) r = m; //porta esta no intervalo [0, m]
            else l = m+1; //porta esta no intervalo [m+1, fim]
        }
        S[l] = 0;
        D[l] = porta;
    }
    else{
        //se der true, nossa porta fica aberta com 1
        //busca binaria no unknown pra encontrar primeiro que der T;
        //1111111100000000000000000000
        //TTTTTTFFFFFFFFFFFFFFFFFF
        //esse ^ daqui eh nosso switch
        int l = 0, r = unknown.size()-1;
        while(l < r){
            int m = (l+r)/2;
            for(int i = 0; i <= m; i++) guess[unknown[i]] = 1;
            for(int i = m+1; i < unknown.size(); i++) guess[unknown[i]] = 0;
            verdic = _tryCombination(guess);
            if(verdic > porta) r = m; //porta esta no intervalo [0, m]
            else l = m+1; //porta esta no intervalo [m+1, fim]
        }
        S[l] = 1;
        D[l] = porta;
    }

}

void exploreCave(int N) {
    n = N;
    S.assign(N, -1);
    D.assign(N, -1);

    for(int i = 0; i < n; i++){
        bsearch(i);
    }

    _answer(S, D);
}

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