Submission #899275

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

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