Submission #1187449

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187449		Mamikonm1	Cave (IOI13_cave)	C++20	100 / 100	356 ms	536 KiB

cave

#include<bits//stdc++.h>
#include "cave.h"
void exploreCave(int n) {
    int s[n]={},d[n]={},cur=0,l,r,md,S[n]={},ind;
    bool vis[n]={};
    for(int i=0;i<n;++i){
        cur=tryCombination(s)==i;
        l=0;r=n-i;
        while(l+1<r){
            md=r+l>>1;
            for(int j=0;j<n;++j)S[j]=s[j];
            for(int j=0,cnt=0;j<n;++j){
                if(!vis[j]){
                    cnt++;
                    if(cnt<=md)S[j]=cur;
                    else S[j]=!cur;
                }
            }
            int x=tryCombination(S);
            if(x==-1)x=n;
            if(x>i)r=md;
            else l=md;
        }
        ind=0;
        for(int cnt=0;cnt<r;++ind){
            if(!vis[ind]){
                ++cnt;
            }
        }
        --ind;
        r=ind;
        d[r]=i;
        s[r]=cur;
        vis[r]=1;
    }
    answer(s,d);
}

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