Submission #1129569

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129569		enzy	Cave (IOI13_cave)	C++20	0 / 100	294 ms	580 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));
        for(int j=0;j<i;j++) ask[pos[j]]=val[j];
        int a=tryCombination(ask), atval;
        if(a==-1||a>i) atval=0; // então o botão da porta i, tem q ser 0
        else atval=1;
        int l=0, r=n-1;
        while(l<r){
            int mid=(l+r)/2;
            if(check(mid,atval,n,i)) r=mid;
            else l=mid+1;
        }
        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