제출 #1289977

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1289977		ChuanChen	동굴 (IOI13_cave)	C++20	0 / 100	231 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){
        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{
        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;
    }
}

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