Submission #1030941

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030941		vjudge1	Cave (IOI13_cave)	C++17	100 / 100	490 ms	860 KiB

cave

#include "cave.h"

#include<bits/stdc++.h>

int n;
int*right,*rightsw,*loc;
int*tryarr;

int tryall(){
    for(int i=0;i<n;i++){
        if(rightsw[i])tryarr[i]=1;
        else tryarr[i]=0;
    }
    return tryCombination(tryarr);
}

int dd;

int tryrange(int l,int r){
    int cnt=0;
    for(int i=0;i<n;i++){
        if(rightsw[i]!=-1){
            tryarr[i]=rightsw[i];
        }else{
            if(l<=cnt&&cnt<=r)tryarr[i]=right[dd];
            else tryarr[i]=!right[dd];
            cnt++;
        }
    }
    return tryCombination(tryarr);
}
int getme(int p){
    int cnt=0;
    for(int i=0;i<n;i++){
        if(rightsw[i]==-1){
            if(cnt==p)return i;
            cnt++;
        }
    }
    //std::cerr<<cnt<<" "<<p<<"\n";
    assert(0 && "nuh uh");
    return -1;
}

int trylr;

void open(int door){
    dd=door;
    if(right[door]==-1){
        int k=tryall();
        if(k==door){
            right[door]=0;
        }else{
            if(k==-1)k=n;
            for(int i=door;i<k;i++){
                right[i]=1;
            }
            if(k!=n){
                right[k]=0;
            }
        }
    }
    int left=n-door;
    int l=0,r=left-1,ans=r;
    while(l<=r){
        int mid=(l+r)>>1;
        int val=tryrange(l,mid);
        if(val==door){
            l=mid+1;
        }else{
            ans=mid;
            r=mid-1;
        }
    }
    //std::cerr<<getme(ans)<<" "<<door<<"\n";
    int sw=getme(ans);
    loc[sw]=door;
    rightsw[sw]=right[door];
}

void exploreCave(int N) {
    n=N;
    right=new int[N],loc=new int[N],tryarr=new int[N],rightsw=new int[N];
    for(int i=0;i<N;i++){
        right[i]=rightsw[i]=loc[i]=-1;
    }
    for(int i=0;i<N;i++){
        open(i);
    }
    answer(rightsw,loc);
}

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