Submission #564497

#	Time	Username	Problem	Language	Result	Execution time	Memory
564497		cpp219	Cave (IOI13_cave)	C++17	0 / 100	612 ms	372 KiB

cave

#include<bits/stdc++.h>
#include"cave.h"
#define ll int
#define ld long double
#define fs first
#define sc second
#define debug(y) cout<<y,exit(0)
using namespace std;
typedef pair<ll,ll> LL;
const ll N = 5e3 + 9;
const ll inf = 1e9 + 7;

ll s[N],d[N],known[N],respon,n;

void ask(){
    respon = tryCombination(s);
    if (respon == -1) respon = inf;
}

void setU(ll l,ll r,ll val){
    for (ll i = 0;i < n;i++)
        if (!known[i]) s[i] = val;
}

void exploreCave(int num){
    n = num;
    for (ll cur = 0;cur < n;cur++){
        setU(0,n - 1,0); ask(); ll now = 1;
        if (respon > cur) now = 0;
        ll l,m,h; l = 0; h = n - 1;
        while(l <= h){
            m = (l + h)/2; setU(0,n - 1,1 - now);
            setU(l,m,now); setU(m + 1,h,1 - now); ask();
            if (respon > cur) h = m - 1;
            else l = m + 1;
        }
        d[l] = cur; s[l] = now; known[l] = 1;
    }
    answer(s,d);
}

/*

int main(){
    ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0);
    #define task "tst"
    if (fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        //freopen(task".out","w",stdout);
    }

}
/// be confident
*/

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