제출 #1129571

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1129571		enzy	동굴 (IOI13_cave)	C++20	0 / 100	1 ms	576 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn=5010;
int pos[maxn], val[maxn]; // pos[i]-> posição do switch que liga a porta i, val[i]-> o estado para abrir a porta i
bool check(int mid, int v, int n, int obj){
    int ask[n];
    for(int i=0;i<mid;i++) ask[i]=v;
    for(int i=mid;i<n;i++) ask[i]=1-v;
    for(int j=0;j<obj;j++) ask[pos[j]]=val[j];
    int x=tryCombination(ask);
    return (x>obj)||(x==-1);
}
void exploreCave(int n){
    int ans1[n], ans2[n];
    for(int i=0;i<n;i++){
        int ask[n];
        memset(ask,0,sizeof(ask)); // começa tudo zero
        for(int j=0;j<i;j++) ask[pos[j]]=val[j]; // deixar as portas anteriores abertas
        int a=tryCombination(ask), atval; // determinar qual eh o estado que abre a porta i, perguntando tudo que sobrou 0
        if(a==-1||a>i) atval=0; // então o botão da porta i, tem q ser 0
        else atval=1; // caso contrário eh 1
        int l=0, r=n-1, ll=-1, lr=-1;
        while(l<r){ // fazer busca binária nos switches para saber qual é a que abre a porta i, (perguntando de 0-(mid-1))
            int mid=(l+r)/2;
            if(check(mid,atval,n,i)) r=mid-1;
            else l=mid;
            assert((ll!=l)&&(lr!=r));
            ll=l; lr=r;
        }
        pos[i]=l;
        val[i]=atval;
        ans1[l]=atval;
        ans2[l]=i;
    }
    answer(ans1,ans2);
}

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