Submission #890082

#	Time	Username	Problem	Language	Result	Execution time	Memory
890082		kokoue	Cave (IOI13_cave)	C++14	0 / 100	260 ms	500 KiB

cave

#include "cave.h"
int bt[5001];
int used[50001];
void exploreCave(int N)
{
    for(int i=0;i<N;i++)
    {
        used[i]=-1;
    }
    int l=0,r=N-1;
    for(int j=0;j<N;j++)
    {
        l=0;
        r=N-1;
        bool fl=0;
        int curr=tryCombination(bt);
        if(curr==j) fl=1;
        while(l!=r)
        {
                int mid=(l+r)/2;
                if((tryCombination(bt)!=j)!=fl)
                {
                    r=mid;
                    mid=(r+l)/2;
                    for(int i=0;i<N;i++)
                    {
                       if(used[i]==-1) bt[i]=0;
                    }
                    for(int i=mid;i<=r;i++)
                    {
                        if(used[i]==-1) bt[i]=1;
                    }
                }
                else
                {
                    l=mid+1;
                    mid=(r+l)/2;
                    for(int i=0;i<N;i++)
                    {
                       if(used[i]==-1) bt[i]=0;
                    }
                    for(int i=mid;i<=r;i++)
                    {
                       if(used[i]==-1) bt[i]=1;
                    }
                }
        }
        used[j]=l;
        if(fl==1) bt[l]=0;
        else bt[l]=1;
   }
   answer(bt,used);
}

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