Submission #372403

#	Time	Username	Problem	Language	Result	Execution time	Memory
372403		amano_hina	Cave (IOI13_cave)	C++14	100 / 100	227 ms	640 KiB

cave

#include "cave.h"

void exploreCave(int n) {
    int a[n],b[n],f[n],mid,ans,ans2,have[n],l,r;
    for(int i=0;i<n;i++)
    {
        f[i]=i;
        a[i]=0;
    }

    for(int i=0;i<n;i++)
    {
        ans=tryCombination(a);
        l=0;
        r=n-1-i;
        while(l<r)
        {
            mid=(l+r)/2;
            for(int j=l;j<=mid;j++)
            {
                a[f[j]]=1-a[f[j]];
            }
            ans2=tryCombination(a);
            if(ans==i)
            {
                if(ans==ans2)
                {
                    l=mid+1;
                }
                else
                {
                    r=mid;
                }
            }
            else
            {
                if(ans2==i)
                {
                    r=mid;
                }
                else
                {
                    l=mid+1;
                }
            }
            
            ans=ans2;

        }
        if(ans==i)
        {
            a[f[l]]=1-a[f[l]];
            
        }
        b[f[l]]=i;
        for(int j=l;j<n-1-i;j++)
        {
            f[j]=f[j+1];
        }


    }
    answer(a,b);

    /* ... */
}

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:4:37: warning: unused variable 'have' [-Wunused-variable]
    4 |     int a[n],b[n],f[n],mid,ans,ans2,have[n],l,r;
      |                                     ^~~~

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