Submission #485149

#	Time	Username	Problem	Language	Result	Execution time	Memory
485149		dekanycsaba	Cave (IOI13_cave)	C++14	100 / 100	185 ms	964 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"
#include<math.h>

void exploreCave(int N) {
   int D[N],S[N]={0};
   int AA[N]={0};
   int a=0,s1=0,s2=0;
   for(int i=0;i<N;i++)
   {
       AA[i]=0;
       D[i]=-1;
   }
   if(N==1)
   {
       s1=tryCombination(AA);
       if(s1>0 || s1==-1)
       {
           a=0;
       }
       else{
            a=1;
       }
       D[0]=0;
       S[0]=a;
       answer(S,D);
   }
   else{

    int k=0,kk=0;
    while(N>pow(2,k))
    {
        k++;
    }
    int nul[k][N]={};
    int egy[k][N]={};
    for(int i=0;i<k;i++)
    {
        for(int j=0;j<N;j++)
        {
             if((j>>i)%2==0)
               {
                   nul[i][j]=0;
                   egy[i][j]=1;
               }
               else{
                    nul[i][j]=1;
                   egy[i][j]=0;
               }
        }
    }

   for(int i=0;i<N;i++)
   {
       s1=tryCombination(AA);
       if(s1>i || s1==-1)
       {
           a=0;
       }
       else{
            a=1;
       }
       kk=0;
       s2=0;
       while(N>pow(2,kk))
       {
           if(a==0)
           {
               s1=tryCombination(nul[kk]);
           }
           else{
            s1=tryCombination(egy[kk]);
           }

            if(s1>i || s1==-1)
            {
               }
            else{
              s2=s2+pow(2,kk);
                }
        kk++;
       }
       D[s2]=i;
       S[s2]=a;
       for(int j=0;j<k;j++)
       {
           nul[j][s2]=a;
           egy[j][s2]=a;
       }
       AA[s2]=a;
   }
   answer(S,D);
   }
}

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