Submission #899302

#	Time	Username	Problem	Language	Result	Execution time	Memory
899302		nasir_bashirov	Cave (IOI13_cave)	C++11	100 / 100	675 ms	600 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];
    vi done(n, 0);
    for(int i = 0; i < n; i++){
        int l = 0, r = n - 1, index = -1, p = -1;
        for(int j = 0; j < n; j++){
            if(done[j]){
                qry[j] = type[j];
            }
            else{
                qry[j] = 0;
            }
        }
        int qq = tryCombination(qry);
        if(qq == -1)    qq = n;
        if(qq >= 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];
                else if(j >= l and j <= mid)    qry[j] = p;
                else    qry[j] = 1 - p;
            }
            int qq = tryCombination(qry);
            if(qq == -1)    qq = n;
            if(qq >= i + 1){
                r = mid - 1;
                index = mid;
            }
            else{
                l = mid + 1;
            }
        }
        done[index] = 1;
        type[index] = p;
        ind[index] = i;
    }
    answer(type, ind);
}

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