제출 #1289983

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1289983		ChuanChen	동굴 (IOI13_cave)	C++20	100 / 100	306 ms	608 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> aux){
    int s[aux.size()];
    for(int i = 0; i < aux.size(); i++)  s[i] = aux[i];
    // cerr << "ASK: ";
    // for(int i = 0; i < S.size(); i++)  cerr << s[i] <<  ' '; cerr << endl;
    int v = tryCombination(s);
    // cerr << "Response: " << v << endl;
    if(v==-1){
        v = n+1;
        // S = aux;
    }
    return v;
    // 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;
    // cerr << "\nSolving porta " << porta << endl;
    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;
        //00x0x00x000x11x111x11x1x
        //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; 
            else l = m+1;
        }
        S[unknown[l]] = 0;
        D[unknown[l]] = porta;
    }
    else{
        //se der true, nossa porta fica aberta com 1
        //busca binaria no unknown pra encontrar primeiro que der T;
        //11x11111x0000x0000x000x00x00
        //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[unknown[l]] = 1;
        D[unknown[l]] = porta;
    }

    // cerr << "What we know:\n";
    // for(int i : S){
    //     cerr << (char)(i==-1? 'x' :  '0'+i) << ' ';
    // }    
    // cerr << endl;
}

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: 12 / 12
• Subtask 2: 13 / 13
• Subtask 3: 21 / 21
• Subtask 4: 30 / 30
• Subtask 5: 24 / 24