Submission #1259472

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259472		truongdz_top12	Cave (IOI13_cave)	C++20	0 / 100	172 ms	504 KiB

cave

#include "cave.h"
#include<bits/stdc++.h>
using namespace std;
int state[5000],door[5000],used[5000],S[5000],D[5000];
void exploreCave(int N)
{
    for(int d=0;d<N;++d)
    {
        for(int i=0;i<N;++i)
            if(used[i])
                S[i]=state[i];
        S[0]^=1;
        int l=0,r=N-1,can=-1;
        int k=tryCombination(S);
        while(l<=r)
        {
            int mid=(l+r)>>1;
            for(int i=0;i<N;++i)
                if(used[i])
                    S[i]=state[i];
                else
                    S[i]=(i<=mid);
            int res=tryCombination(S);
            if(res==-1||res>d)
            {
                can=mid;
                r=mid-1;
            }
            else
                l=mid+1;
        }
        used[can]=1;
        D[can]=d;
        for(int s=0;s<=1;++s)
        {
            S[can]=s;
            for(int i=0;i<N;++i)
                if(used[i]&&i!=can)
                    S[i]=state[i];
            int res=tryCombination(S);
            if(res==-1||res>d)
            {
                state[can]=s;
                break;
            }
        }
    }
    answer(state,D);
}

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