Submission #16070

#	Time	Username	Problem	Language	Result	Execution time	Memory
16070		ggoh	Cave (IOI13_cave)	C++98	0 / 100	177 ms	516 KiB

cave

#include<cstdio>
#include "cave.h"
  

void exploreCave(int N)
{
	int D[5555]={},S[5555]={},s[5555]={};
	bool C[5555]={};
    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