Submission #303797

#	Time	Username	Problem	Language	Result	Execution time	Memory
303797		MasterTaster	Cave (IOI13_cave)	C++14	100 / 100	1290 ms	628 KiB

cave

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

#define pb push_back
#define ll long long
#define pii pair<int, int>
#define xx first
#define yy second

using namespace std;

///int tryCombination(intS[]);

bool nadjen[5010];
int N;

void exploreCave(int N) {

    int znak[5010];
    int n=N;
    int gde[5010], koga[5010];
    for (int i=0; i<n; i++)
    {
        for (int j=0; j<n; j++) if (!nadjen[j]) znak[j]=0;

        int koja=tryCombination(znak);

        ///ispisi(znak);

        int trZnak;///=(int)(koja!=-1 && koja<=i);
        if (koja==-1 || koja>i) trZnak=0;
        else trZnak=1;

        ///cout<<i<<" "<<koja<<" "<<trZnak<<endl;

        int l=0, r=n-1;
        while (l<=r)
        {
            int mid=l+(r-l)/2;
            for (int j=0; j<n; j++) if (!nadjen[j]) { if (j<=mid) znak[j]=trZnak; else znak[j]=1-trZnak; }
            ///cout<<mid<<":"<<endl;
            ///ispisi(znak);
            ///cout<<tryCombination(znak)<<endl;
            int kombinacija=tryCombination(znak);
            if (kombinacija>i || kombinacija==-1)
            {
                gde[i]=mid;
                r=mid-1;
            }
            else l=mid+1;
        }
        znak[gde[i]]=trZnak;
        nadjen[gde[i]]=true;
        koga[gde[i]]=i;

        ///cout<<"gde? "<<gde[i]<<endl;
    }

    answer(znak, koga);
}

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