Submission #1320797

#	Time	Username	Problem	Language	Result	Execution time	Memory
1320797		yessimkhan	Cave (IOI13_cave)	C++20	100 / 100	169 ms	516 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
// solved by bekagg
#define ll long long
#define ent '\n'
#define pb push_back
#define all(x) x.begin(),x.end()
#define PRaim_bek_abi ios_base::sync_with_stdio(0);cin.tie(0);

using namespace std;

const int N = 5e3+5;
const int MOD = 1e9+7;

int s[N] , d[N] , us[N] , nn;

bool t;

void build(int tl , int tr , int i){
    if (tl == tr){
        if (t){
            d[tl] = i;
            us[tl] = 1; 
        }
        else {
            s[tl] = 1 - s[tl];
            d[tl] = i;
            us[tl] = 1;
        }
        return;
    }

    int tm = (tl + tr) / 2;

    for (int i = tl; i <= tm; i++){
        if (us[i]) continue;
        s[i] = 1 - s[i];
    }

    int pos = tryCombination(s);
    pos = (pos == -1 ? nn : pos);

    for (int i = tl; i <= tm; i++){
        if (us[i]) continue;
        s[i] = 1 - s[i];
    }

    if (t){
        if (pos <= i){
            build(tl , tm , i);
        }
        else {
            build(tm + 1 , tr , i);
        }
    }
    else {
        if (pos > i){
            build(tl , tm , i);
        }
        else {
            build(tm + 1 , tr , i);
        }
    }
}


void exploreCave(int n){

    nn = n;

    for (int i = 0; i < n; i++){
        t = 0;
        int pos = tryCombination(s);
        pos = (pos == -1 ? n : pos);
        if (pos > i) t = 1;
        build(0 , n - 1 , i);
    }

    answer(s , d);
}

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