Submission #387018

#	Time	Username	Problem	Language	Result	Execution time	Memory
387018		Carmel_Ab1	The Big Prize (IOI17_prize)	C++17	0 / 100	1365 ms	1048580 KiB

prize

#include <bits/stdc++.h>
#include "prize.h"
//#include "grader.cpp"
using namespace std;
typedef long long ll;
typedef vector<ll>vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pl;
typedef vector<pl> vpl;
typedef vector<int> vi;
typedef vector<vi>vvi;

#define all(x) x.begin(),x.end()
#define print(x) {for(auto it:x) cout << it << " " ;cout << "\n";}
#define out(x) {cout << x << "\n"; return;}
#define GLHF ios_base::sync_with_stdio(false); cin.tie(NULL)

vvi mp;
vi get(int i){
    if(mp[i].size())return mp[i];
    return mp[i]=ask(i);
}

int rec(int l,int r,int i){
    if(l>r)return -1;
    vi aski=get(i);
    int m=(l+r)/2;
    vi askm=get(m);

    if(aski[0]+aski[1]>askm[0]+askm[1])return m;
    else if(l==r)return -1;

    int lp=rec(l,m,i);
    if(lp!=-1)return lp;

    int rp=rec(m,r,i);
    if(rp!=-1)return rp;
    return -1;
}
int find_smaller(int n,int i){
    vi aski=get(i);
    if(aski[0]==0 && aski[1]==0)return i;
    if(aski[0])return rec(0,i-1,i);
    else return rec(i+1,n-1,i);
}
int find_best(int n){
    mp.resize(n);
    int ans=0;
    for(int i=0; i<6; i++)
        ans=find_smaller(n,ans);
    return ans;
}
/*
9
1 3 3 2 3 3 3 2 3
 */

• Subtask 1: 0 / 20
• Subtask 2: 0 / 80