Submission #1247907

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247907		denislav	Cave (IOI13_cave)	C++20	12 / 100	137 ms	512 KiB

cave

# include <iostream>
# include <vector>
using namespace std;
# include "cave.h"
//# include "grader.c"

const int MAX=5e3+11;

int query(int S[])
{
    int resp=tryCombination(S);
    if(resp==-1) return 1e9;
    else return resp;

}

void exploreCave(int N)
{
    int s[N+1],d[N+1];
    for(int i=0;i<N;i++)
    {
        s[i]=0;
        d[i]=-1;
    }

    for(int i=0;i<N;i++)
    {
        int resp=query(s);
        int l=0,r=N-1,ans=0;
        while(l<r)
        {
            int mid=(l+r)/2;
            for(int i=l;i<=mid;i++) if(d[i]==-1) s[i]^=1;
            int resp2=query(s),L=i;
            if((resp==i and resp2==i) or (resp>i and resp2>i))
            {
                l=mid+1;
                ans=mid+1;
            }
            else
            {
                r=mid;
                ans=mid;
            }

            for(int i=L;i<=mid;i++) if(d[i]==-1) s[i]^=1;
        }

        d[ans]=i;
        if(resp==i) s[ans]=1;
    }

    answer(s,d);
}

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