Submission #891279

#	Time	Username	Problem	Language	Result	Execution time	Memory
891279		presko	Cave (IOI13_cave)	C++14	100 / 100	594 ms	1052 KiB

cave

#include "cave.h"
bool found[6000];
int state[6000];
int swtch[6000];
bool start[6000];
int s[6000];
int ga[6000];
int fil(int ind,int n)
{
    int l=0,r=n-1;
    while(r!=l)
    {
        int mid=(l+r+1)/2;
        for(int i=0;i<n;i++)
        {
            if(found[i]){s[i]=state[i];continue;}
            if(i<mid)s[i]=1;
            else s[i]=0;
        }
        int ans=tryCombination(s);
        bool sta=0;
        if(ans>ind || ans==-1)sta=1;
        if(sta!=start[ind])r=mid-1;
        else l=mid;
    }
    swtch[l]=ind;
    found[l]=1;
    if(start[ind]==1)state[l]=0;
    else state[l]=1;
    return l;
}
void exploreCave(int N)
{
    for(int i=0;i<N;i++)
    {
        int res=tryCombination(ga);
        if(res==-1)res=N;
        for(int j=0;j<res;j++)start[j]=1;
        for(int j=res;j<N;j++)start[j]=0;
        int x=fil(i,N);
        ga[x]=state[x];
    }
    answer(state,swtch);
}

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