Submission #1203591

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203591		a.pendov	Cave (IOI13_cave)	C++20	100 / 100	194 ms	588 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;

void exploreCave(int N)
{
    int s[N];
    int des[N];
    int key[N];

    for(int i=0;i<N;i++)
    {
        s[i]=0;
        des[i]=0;
    }

    for(int i=0;i<N;i++)
    {
        int curr;
        vector<int> v;
        for(int j=0;j<N;j++)
        {
            if(des[j])continue;
            v.push_back(j);
            s[j]=0;
        }

        if(tryCombination(s)==i)curr=1;
        else curr=0;

        int l=0,r=N-i-1;
        while(l+1<r)
        {
            int mid=(l+r)/2;
            for(int k=0;k<=mid;k++)s[v[k]]=curr;
            for(int k=mid+1;k<v.size();k++)s[v[k]]=1-curr;

            if(tryCombination(s)==i)
            {
                l=mid+1;
            }
            else
            {
                r=mid;
            }
        }
        for(int k=0;k<l+1;k++)s[v[k]]=curr;
        for(int k=l+1;k<v.size();k++)s[v[k]]=1-curr;

        if(tryCombination(s)==i)
        {
            des[v[l+1]]=1;
            key[v[l+1]]=i;
            s[v[l+1]]=curr;
        }
        else
        {
            des[v[l]]=1;
            key[v[l]]=i;
            s[v[l]]=curr;
        }

    }

    answer(s,key);
}

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