Submission #1245260

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245260		boyan2010	Cave (IOI13_cave)	C++20	100 / 100	183 ms	596 KiB

cave

#include<bits/stdc++.h>
#include "cave.h"
using namespace std;
int s[5007],d[5007],temps[5007],n;
bool u[5007];
void f(int i)
{
    vector<int>left;
    for(int j=0;j<n;j++)
    {
        if(u[j])
        {
            temps[j]=s[j];
        }
        else
        {
            left.push_back(j);
            temps[j]=0;
        }
    }
    int temp=tryCombination(temps);
    bool type;
    if(temp>i || temp==-1)
    {
        type=0;
    }
    else
    {
        type=1;
    }
    int l=0,r=left.size()-1;
    while(r>=l)
    {
        int m=(l+r)/2;
        for(auto el:left)
        {
            temps[el]=(!type);
        }
        for(int j=l;j<=m;j++)
        {
            temps[left[j]]=type;
        }
        temp=tryCombination(temps);
        if(temp>i || temp==-1)
        {
            r=m-1;
        }
        else
        {
            l=m+1;
        }
    }
    u[left[l]]=1;
    d[left[l]]=i;
    s[left[l]]=type;
}
void exploreCave(int N)
{
    n=N;
    for(int i=0;i<n;i++)
    {
        f(i);
    }
    answer(s,d);
}

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