Submission #1291857

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291857		hssaan_arif	Cave (IOI13_cave)	C++20	100 / 100	418 ms	552 KiB

cave

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

#define endl "\n"
#define pb push_back
// #define int long long
#define fi first
#define se second

int n , S[5005] = {} , D[5005] = {} , V[5005] , T[5005];

void doit(int l , int r , int t){
    for (int i=0 ; i<n ; i++){
        if (T[i]!=-1){
            // cout << T[i] << ' ';
            continue;
        }
        if (l <= i && i <= r){
            T[i] = t;
        }else{
            T[i] = !t;
        }
    }
}
void exploreCave(int N) {
    n = N;
    for (int i=0;i<n;i++) S[i] = -1;
    for (int i=0 ; i<n ; i++){
        int l=0 , r=n-1;
        int u = tryCombination(V);
        bool ty = 0;
        if (u==-1 || u > i){

        }else{
            ty = 1;
        }
        while(l <= r){
            int mid = (l+r)>>1;
            for (int k=0;k<n;k++) T[k] = S[k];
            doit(l,mid,ty);
            int u = tryCombination(T);
            // cout << l << ' ' << mid << ' ' << u << endl;
            if (u > i || u == -1){
                r = mid-1;
            }else{
                l = mid+1;
            }
        }
        // cout << ty << ' ' << l << endl;
        D[l] = i;
        V[l] = ty;
        S[l] = ty;
    }
    
    answer(S , D);
}

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