Submission #250215

#	Time	Username	Problem	Language	Result	Execution time	Memory
250215		MarcoMeijer	Cave (IOI13_cave)	C++14	100 / 100	918 ms	804 KiB

cave

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

//macros
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define INF 1e9
#define pb push_back
#define fi first
#define se second
#define sz size()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

//===================//
//  Added libraries  //
//===================//

//===================//
//end added libraries//
//===================//

const int MX = 5100;

int n;
int mask[MX], comb[MX], temp[MX];
int con[MX];

int ask(int lb, int ub, bool open) {
    RE(i,n) {
        if(mask[i]) temp[i] = comb[i];
        else temp[i] = (lb <= i && i <= ub) ^ open ^ true;
    }
    int ret = tryCombination(temp);
    if(ret == -1) ret = n;
    return ret;
}

void exploreCave(int N) {
    n = N;
    RE(i,n) mask[i] = 0;
    RE(i,n) {
        int lb=0, ub=N-1;
        bool open = (ask(lb, ub, 1) > i);
        while(lb != ub) {
            int mid=(lb+ub)/2;
            if(ask(lb, mid, open) > i) ub=mid;
            else lb=mid+1;
        }
        mask[lb] = 1;
        comb[lb] = open;
        con[lb] = i;
    }
    answer(comb, con);
}

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