Submission #964664

#	Time	Username	Problem	Language	Result	Execution time	Memory
964664		marinaluca	Cave (IOI13_cave)	C++17	100 / 100	630 ms	600 KiB

cave

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

#pragma GCC optimize ("O4")
#pragma GCC optimize ("fast-math")
#pragma GCC optimize ("unroll-loops")

using namespace std;
/**
#define int long long
#define ll long long
#define all (x) begin(x), end(x)
#define xx first
#define yy second
#define cin fin
#define cout fout
typedef db double;
typedef ldb long double;
typedef vii vector <int>;
typedef pii pair <int, int>;
typedef pai pair <double, double>;
ifstream cin ("cave.in");
ofstream cout ("cave.out");
**/
typedef long long ll;
const int NMAX = 5e3;
ll n;
int usa[NMAX + 1];
int sus[NMAX + 1];

void intoarce (ll val){
    for (int i = 0; i <= val; ++ i){
        if (usa[i] == -1)
            sus[i] ^= 1;
    }
}

void init_switches (){
    for (int i = 0; i < n; ++ i){
        usa[i] = -1;
        sus[i] = 0;
    }
}

bool solve (int k, int poz){
    intoarce(k);
    ll rez = tryCombination(sus);
    intoarce (k);
    return rez == poz;
}
void exploreCave (int N){
    n = N;
    init_switches();
    for (int i = 0; i < n; ++ i){
        ll cur = tryCombination(sus);
        if (cur == i){
            intoarce (n - 1);
        }
        ll st = 0;
        ll  dr = n - 1;
        ll Answer = -1;
        ll mijl;
        while (st <= dr){
            mijl = (st + dr) >> 1;
            if (solve(mijl, i)){
                Answer = mijl;
                dr = mijl - 1;
            }
            else
                st = mijl + 1;
        }
        usa[Answer] = i;
    }
    answer (sus, usa);
}

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