Submission #899266

#	Time	Username	Problem	Language	Result	Execution time	Memory
899266		aykhn	Cave (IOI13_cave)	C++17	0 / 100	362 ms	528 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
 
#define db long double
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define vll vector<pll>
#define endl '\n'
#define all(x) x.begin(), x.end()
#define fastio\
    ios_base::sync_with_stdio(0);\
    cin.tie(0);\
    cout.tie(0)\
 
void exploreCave(int n){
    int type[n], ind[n], qry[n];
	vector<int> done(n, 0);
    for(int i = 0; i < n; i++){
        int l = 0, r = n - 1, p;
        for(int j = 0; j < n; j++){
            if(done[j]){
                qry[j] = type[j];
            }
            else{
                qry[j] = 0;
            }
        }
        if(tryCombination(qry) >= i + 1){
            p = 0;
        }
        else{
            p = 1;
        }
        while(l < r){
            int mid = (l + r) / 2;
            for(int j = 0; j < n; j++){
                if(done[j]){
                    qry[j] = type[j];
                  	continue;
                }
              	if (l <= j && j <= mid){
                  	qry[j] = p;
                }
              	else qry[j] = 1 - p;
            }
            if(tryCombination(qry) >= i + 1){
                r = mid;
            }
            else{
                l = mid + 1;
            }
        }
        done[l] = 1;
        type[l] = p;
        ind[l] = i;
    }
    answer(type, ind);
}

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