Submission #441245

#	Time	Username	Problem	Language	Result	Execution time	Memory
441245		FEDIKUS	동굴 (IOI13_cave)	C++17	100 / 100	1123 ms	644 KiB

cave

#include "cave.h"

const int maxn=5010;

int s[maxn];
int d[maxn];
bool resio[maxn];
int ns[maxn];

int pitaj(int k,int sta,int n){
    for(int i=0;i<n;i++){
        if(resio[i]){
            ns[i]=s[i];
            continue;
        }
        if(i<=k) ns[i]=sta;
        else ns[i]=1-sta;
    }
    int ret=tryCombination(ns);
    if(ret==-1) ret=n;
    return ret;
}

void exploreCave(int n) {
    for(int i=0;i<n;i++){
        int sta=-1;
        if(pitaj(n,1,n)>i) sta=1;
        else sta=0;
        
        int l=0;
        int r=n;
        int gde=-1;
        while(l<=r){
            int mid=l+(r-l)/2;
            if(pitaj(mid,sta,n)>i){
                gde=mid;
                r=mid-1;
            }else l=mid+1;
        }
        d[gde]=i;
        s[gde]=sta;
        resio[gde]=true;
    }
    answer(s,d);
}

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