Submission #65013

#	Time	Username	Problem	Language	Result	Execution time	Memory
65013		theknife2001	Cave (IOI13_cave)	C++17	100 / 100	893 ms	640 KiB

cave

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

using namespace std;
const int NN=5e3+55;
int a[NN];
int p[NN];
int d[NN];

void exploreCave(int n)
{
    memset(d,-1,sizeof d);
    memset(p, 0,sizeof p);
    for(int i=0;i<n;i++)
    {
        int x;
        for(int j=0;j<n;j++)
            a[j]=p[j];
        int q=tryCombination(a);
        if(q==-1)
            q=n;
        int l=0,r=n,mid;
//        cout<<q<<endl;
        while(l<r)
        {
            for(int j=0;j<n;j++)
                a[j]=p[j];
            mid=(l+r)/2;
            for(int j=0;j<mid;j++)
            {
                if(d[j]!=-1)
                    continue ;
                a[j]=1;
            }
            x=tryCombination(a);
            if(x==-1)
                x=n;
//            for(int j=0;j<n;j++)
//                cout<<a[j]<<' ';
//            cout<<endl;
//            cout<<mid<<' '<<x<<endl;
            if((q>i&&x==i)||(q==i&&x>i))
                r=mid;
            else
                l=mid+1;
        }
        if(q>i)
        {
            d[l-1]=i;
            p[l-1]=0;
        }
        else if(q==i)
        {
            d[l-1]=i;
            p[l-1]=1;
        }
//        for(int j=0;j<n;j++)
//            cout<<p[j]<<' ';
//        cout<<endl;
    }
    answer(p,d);
}

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