Submission #1080683

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080683		Gray	Cave (IOI13_cave)	C++17	100 / 100	533 ms	604 KiB

cave

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

using namespace std;

#define ll int
#define ff first
#define ss second
#define ln "\n"

ll n;

ll S[5000], D[5000];
ll ar[5000];
ll excl[5000];
ll ask(ll ind){
    for (ll i=0; i<n; i++) {
        if (excl[i]) ar[i]=S[i];
        else ar[i]=0;
    }
    for (ll i=0; i<=ind; i++){
        if (excl[i]) continue;
        else ar[i]=1;
    }
    // for (ll i=0; i<n; i++) cout << ar[i] << " ";
    // cout << " :: " << tryCombination(ar) << ln;
    return tryCombination(ar);
}
void exploreCave(int N) {
    n=N; 
    memset(S, 0, sizeof S); memset(D, 0, sizeof D);
    memset(excl, 0, sizeof excl);
    ll ind=tryCombination(S);
    for (ll i=0; i<N; i++){
        ll l=-1, r=N-1;
        while (l+1<r){
            ll mid = (l+r)/2;
            ll ret=ask(mid);
            if ((ind==i and ret!=i) or (ind!=i and ret==i)) r=mid;
            else l=mid; 
        }
        // cout << ind << ":" << r << ln;
        if (ind==i) S[r]=1;
        else S[r]=0;
        D[r]=i;
        excl[r]=1;
        ind=tryCombination(S);
    }
    answer(S, D);
}

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