Submission #1080672

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080672		Gray	Cave (IOI13_cave)	C++17	0 / 100	617 ms	564 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 ask(ll ind, set<ll> &excl){
    for (ll i=0; i<n; i++) ar[i]=0;
    for (ll i=0; i<ind; i++){
        if (excl.count(i)) ar[i]=S[i];
        else ar[i]=1;
    }
    return tryCombination(ar);
}
void exploreCave(int N) {
    n=N; memset(S, 0, sizeof S); memset(D, 0, sizeof D);
    set<ll> excl;
    ll ind=tryCombination(S);
    for (ll i=0; i<N; i++){
        ll l=-1, r=N;
        while (l+1<r){
            ll mid = (l+r)/2;
            ll ret=ask(mid, excl);
            if ((ind==i and ret!=i) or (ind!=i and ret==i)) r=mid;
            else l=mid; 
        }
        if (ind==i) S[r]=1;
        else S[r]=0;
        D[i]=r;
        excl.insert(r);
        ind=tryCombination(S);
    }
    answer(S, D);
}

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