Submission #764907

#	Time	Username	Problem	Language	Result	Execution time	Memory
764907		fatemetmhr	Cave (IOI13_cave)	C++17	100 / 100	464 ms	536 KiB

cave

//  ~ Be Name Khoda ~  //

#include "cave.h"
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  1e6   + 10;
const int maxn5 =  5e3   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   + 7;
const ll  inf   =  1e18;

int n, ask[maxn5], mat[maxn5];
int cor[maxn5], av[maxn5];
bool det[maxn5];

inline int check(int l, int r, int ty){
    for(int i = 0; i < n; i++){
        if(det[i])
            ask[i] = cor[i];
        else
            ask[i] = (l > i || i >= r) ^ ty;
    }
    return tryCombination(ask);
}

void exploreCave(int N) {
    n = N;
    memset(det, false, sizeof det);
    for(int i = 0; i < n; i++){
        int pt = 0;
        for(int j = 0; j < n; j++){
            if(!det[j]){
                av[pt++] = j;
                ask[j] = true;
            }
            else
                ask[j] = cor[j];
        }
        av[pt] = maxn5;
        int last = tryCombination(ask);
        bool ty = (last != i);
        int lo = 0, hi = pt;
        while(hi - lo > 1){
            int mid = (lo + hi) >> 1;
            if(i != check(av[lo], av[mid], ty))
                hi = mid;
            else
                lo = mid;
        }
        cor[av[lo]] = ty;
        mat[av[lo]] = i;
        det[av[lo]] = true;
        //cout << "found " << i << ' ' << ty << ' ' << lo << ' ' << hi << ' ' << pt << ' ' << av[lo] << endl;
    }

    answer(cor, mat);
}

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