Submission #890253

#	Time	Username	Problem	Language	Result	Execution time	Memory
890253		kokoue	Cave (IOI13_cave)	C++14	100 / 100	578 ms	604 KiB

cave

#include "cave.h"
int bt[5001];
int used[5001];
int right[5001];
bool used_key[5001];
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;
      //  int mid=(l+r)/2;
        bool fl=0;
        for(int i=0;i<N;i++)
        {
            if(used_key[i]==0) bt[i]=0;
        }
        int curr=tryCombination(bt);
        if(curr==j) fl=1;
        while(l!=r)
        {
                int mid=(l+r)/2;
                for(int i=0;i<N;i++)
                {
                    if(used_key[i]==0) bt[i]=0;
                }
                for(int i=l;i<=mid;i++)
                {
                    if(used_key[i]==0) bt[i]=1;
                }
                if((tryCombination(bt)!=j)!=fl)
                {
                    l=mid+1;
                }
                else
                {
                   // l=mid+1;
                   r=mid;
                }
        }
        used[j]=l;
        used_key[l]=true;
        if(fl==1) bt[l]=1;
        else bt[l]=0;
      //  printf("%dth bit is %d and used[%d]=%d\n",l,bt[l],j,used[j]);
   }
   for(int i=0;i<N;i++)
   {
       right[used[i]]=i;
   }
   answer(bt,right);
}

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