Submission #1350602

#	Time	Username	Problem	Language	Result	Execution time	Memory
1350602		feyza	동굴 (IOI13_cave)	C++20	100 / 100	270 ms	556 KiB

cave

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

using namespace std;

const int maxn=5005;
int n;
int doorbit[maxn];
int usedswitch[maxn];

void exploreCave(int N)
{
    n=N;

    int ans[N],bit[N];

    for(int i=0;i<N;i++)
    {
        bit[i]=0;
        ans[i]=0;
    }

    int ask[N];

    for(int i=0;i<N;i++)
    {
        int c=tryCombination(bit);
        if(c==-1)
            c=N;
        if(c>i)
            doorbit[i]=0;
        else
            doorbit[i]=1;

        int curr;
        int l=0,r=N-1,mid;
        while(l<=r)
        {
            mid=(l+r)/2;

            for(int j=0;j<=mid;j++)
            {
                if(usedswitch[j])
                    ask[j]=doorbit[ans[j]];
                else
                    ask[j]=doorbit[i];
            }
            for(int j=mid+1;j<N;j++)
            {
                if(usedswitch[j])
                    ask[j]=doorbit[ans[j]];
                else
                    ask[j]=1-doorbit[i];
            }

            curr=tryCombination(ask);
            if(curr==-1)
                curr=N;

            if(curr>i)
                r=mid-1;
            else
                l=mid+1;
        }

        ans[l]=i;
        usedswitch[l]=1;
        bit[l]=doorbit[i];
    }

    /*cout<<"bit ";
    for(int i=0;i<N;i++)
        cout<<bit[i]<<' ';
    cout<<endl;
    cout<<"ans ";
    for(int i=0;i<N;i++)
        cout<<ans[i]<<' ';
    cout<<endl;*/

    answer(bit,ans);
}

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