Submission #539310

#	Time	Username	Problem	Language	Result	Execution time	Memory
539310		andrei_boaca	Cave (IOI13_cave)	C++17	100 / 100	922 ms	592 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"
//#pragma GCC optimize("O3")
//#include "grader.c"
using namespace std;
int S[5005],D[5005],cnt;
bool use[5005];
void exploreCave(int n)
{
    for(int i=0;i<n;i++)
    {
        int val=0;
        for(int j=0;j<n;j++)
            if(!use[j])
                S[j]=0;
        int nr=tryCombination(S);
        //cnt++;
        if(nr==-1||nr>i)
            val=0;
        else
            val=1;
        int st=0;
        int dr=n-1;
        int poz=-1;
        while(st<=dr)
        {
            int mij=(st+dr)/2;
            for(int j=0;j<=mij;j++)
                if(!use[j])
                    S[j]=val;
            for(int j=mij+1;j<n;j++)
                if(!use[j])
                    S[j]=(val+1)%2;
            nr=tryCombination(S);
            //cnt++;
            if(nr==-1||nr>i)
            {
                poz=mij;
                dr=mij-1;
            }
            else
                st=mij+1;
        }
        S[poz]=val;
        use[poz]=1;
        D[poz]=i;
    }
    //cout<<cnt<<'\n';
    answer(S,D);
}

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