Submission #16067

#	Time	Username	Problem	Language	Result	Execution time	Memory
16067		ggoh	Cave (IOI13_cave)	C++98	0 / 100	194 ms	524 KiB

cave

#include<cstdio>
#include "cave.h"
 
int D[5555],S[5555],s[5555];
bool C[5555];
void exploreCave(int N)
{
    int i,p,q,h,back,ima;
    for(i=0;i<N;i++)
    {
        p=0;q=N;
        for(int j=0;j<N/2;j++)
        {
            if(C[j])s[j]=S[j];
            else s[j]=0;
        }
        back=tryCombination(s);
        if(back==-1)back=N;
        while(p!=q-1)
        {
            h=(p+q)/2;
            for(int j=p;j<h;j++)
            {
                if(C[j])s[j]=S[j];
                else s[j]=1-s[j];
            }
            ima=tryCombination(s);
            if(ima==-1)ima=N;
            if((ima>i&&back>i)||(ima==i&&back==i))
            {
                back=ima;
                p=h;
            }
            else
            {
                back=ima;
                q=h;
            }
        }
        if(back==i)S[p]=1-s[p];
        else S[p]=s[p];
        D[p]=i;
        C[p]=1;
    }
    answer(S,D);
}

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