Submission #922416

#	Time	Username	Problem	Language	Result	Execution time	Memory
922416		HuyQuang_re_Zero	The Big Prize (IOI17_prize)	C++14	100 / 100	27 ms	3588 KiB

prize

#include <bits/stdc++.h>
#define ll long long
#define db long double
#define N 200005
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define IDB pair <db,int>
#define TII pair <treap*,treap*>
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x)
using namespace std;
#include "prize.h"
struct Interactive
{
    int a[N],n;
    void Init(int _n)
    {
        n=_n;
        for(int i=0;i<n;i++) cin>>a[i];
    }
    vector <int> ask(int u)
    {
        vector <int> res; res.resize(2);
        for(int i=0;i<u;i++) res[0]+=(a[i]<a[u]);
        for(int i=u+1;i<n;i++) res[1]+=(a[i]<a[u]);
        return res;
    }
} IR;
//vector <int> ask(int u) { return IR.ask(u); }

int Before[N],After[N];
void quest(int u)
{
    vector <int> vec=ask(u);
    Before[u]=vec[0]; After[u]=vec[1];
}
bool Is_Diamond(int u)
{
    return Before[u]+After[u]==0;
}
int Find_Diamond(int l,int r)
{
    if(r-l<=1) return -1;
    if(Before[l]+After[l]==Before[r]+After[r])
    {
        if(Before[r]==Before[l]) return -1;
        int mid=(l+r)>>1;
        quest(mid);
        if(Is_Diamond(mid)) return mid;
        int k=Find_Diamond(l,mid);
        if(k>-1) return k;
        return Find_Diamond(mid,r);
    }
    else if(Before[l]+After[l]<Before[r]+After[r])
    {
        quest(l+1);
        if(Is_Diamond(l+1)) return l+1;
        return Find_Diamond(l+1,r);
    }
    else
    {
        quest(r-1);
        if(Is_Diamond(r-1)) return r-1;
        return Find_Diamond(l,r-1);
    }
}
int find_best(int n)
{
    quest(0);
    if(Is_Diamond(0)) return 0;
    quest(n-1);
    if(Is_Diamond(n-1)) return n-1;
    return Find_Diamond(0,n-1);
}
/*
int main()
{
    freopen("prize.inp","r",stdin);
    freopen("prize.out","w",stdout);
    int n;
    cin>>n;
    IR.Init(n);
    cout<<find_best(n);
}
*/

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