Submission #526793

#	Time	Username	Problem	Language	Result	Execution time	Memory
526793		ToroTN	Cave (IOI13_cave)	C++14	100 / 100	1006 ms	548 KiB

cave

#include<stdio.h>
#include "cave.h"
int n,hsh[5005],st,md,ed,a[5005],b[5005],val,c[5005];
void exploreCave(int N) {
    /* ... */
    n=N;
    for(int i=0;i<n;i++)
    {
        hsh[i]=-1;
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(hsh[j]==-1)
            {
                a[j]=0;
            }else
            {
                a[j]=hsh[j];
            }
        }
        val=0;
        if(tryCombination(a)!=i)
        {
            val=1;
            for(int j=0;j<n;j++)
            {
                if(hsh[j]==-1)
                {
                    a[j]=1;
                }else
                {
                    a[j]=hsh[j];
                }
            }
        }
        /*printf("tungton= ");
        for(int j=0;j<n;j++)
        {
            printf("%d ",a[j]);
        }
        printf("\n");
        printf("tryCombination=%d\n",tryCombination(a));*/
        st=0;
        ed=n-1;
        while(ed>=st)
        {
            md=(st+ed)/2;
            //printf("%d %d %d\n",st,md,ed);
            for(int j=0;j<n;j++)
            {
                if(hsh[j]!=-1)
                {
                    b[j]=hsh[j];
                }else
                {
                    if(j<=md)
                    {
                        b[j]=1-a[j];
                    }else
                    {
                        b[j]=a[j];
                    }
                }
            }
            /*for(int j=0;j<n;j++)
            {
                printf("%d ",b[j]);
            }
            printf("\n");
            printf("%d\n",tryCombination(b));*/
            if(tryCombination(b)!=i)
            {
                ed=md-1;
            }else
            {
                st=md+1;
            }
            //printf("final=%d %d %d\n",st,md,ed);
        }
        hsh[st]=1-val;
        //printf("%d %d %d\n",st,md,ed);
        c[st]=i;
        /*printf("fuckyou=%d %d\n",val,st);
        printf("hash\n");
        for(int j=0;j<n;j++)
        {
            printf("%d ",hsh[j]);
        }
        printf("\n");*/
    }
    /*for(int i=0;i<n;i++)
    {
        printf("%d ",hsh[i]);
    }
    printf("\n");
    for(int i=0;i<n;i++)
    {
        printf("%d ",c[i]);
    }
    printf("\n");*/
    answer(hsh,c);
}

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