Submission #965638

#	Time	Username	Problem	Language	Result	Execution time	Memory
965638		Amr	Cave (IOI13_cave)	C++17	100 / 100	687 ms	848 KiB

cave

#include "cave.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int NN = 5002;
ll vis[NN];
ll ans[NN];
ll n;
ll ask(ll l ,ll r)
{
    int v[n];
    for(int i = 0; i < n; i++)
    {
        if(vis[i]==0)
        {
            if(i>=l&&i<=r)
                v[i] = 1;
            else v[i] = 0;
        }
        else if(vis[i]==1) v[i] = 1;
        else v[i] = 0;
    }
    return tryCombination(v);
}
void answ()
{
    int v[n], an[n];
    for(int i = 0; i < n; i++) v[i] = vis[i] , an[i] = ans[i];
    answer(v,an);
}

void exploreCave(int N) {
    n= N;
    for(int i = 0; i < N; i++) ans[i] = -1;
    for(int i = 0; i <N; i++)
    {
        ll l = 0, r = N;
        ll lst = ask(0,-1);
        lst = (lst==-1||lst>i);
        //cout << lst << " ";
        while(l+1<r)
        {
            ll mid = (l+r)/2;
            ll cur = ask(l,mid-1);
            cur = (cur==-1||cur>i);
          //  cout << cur << " ";
            if(cur!=lst) r = mid;
            else l = mid;
        }
        //cout << l << endl;
        ans[l] = i;
        if(lst==1) vis[l] = 2; else vis[l] = 1;
    }
    for(int i = 0; i < N; i++) if(vis[i]==2) vis[i] = 0;
    answ();


}

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