Submission #526332

#	Time	Username	Problem	Language	Result	Execution time	Memory
526332		leaked	The Big Prize (IOI17_prize)	C++14	100 / 100	54 ms	352 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>


#define f first
#define s second
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define m_p make_pair
#define sz(x) (int)(x).size()
#define pw(x) (1LL<<(x))
//#define pragma optimize("unroll-loops")
using namespace std;
const int N=2e5+1;
typedef pair<int,int> pii;
template <class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template <class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
bool used[N];
map<int,int> lft,rgt;
int rec(int l,int r,map<int,int> cur){
    if(l>r) return -1;
    if(l==r){
        vec<int> me=ask(l);
        if(me[0]+me[1]==0)
            return l;
        lft[me[0]+me[1]]=me[1];
        for(auto &z : lft){
            if(z.f>me[0]+me[1])
                ++z.s;
        }
        return -1;
    }
    int tm=(l+r)>>1;
    vec<int> me=ask(tm);
    if(me[0]+me[1]==0)
        return tm;
    int hv=me[1]-(lft.count(me[0]+me[1])?lft[me[0]+me[1]]:0);
    if(hv){
        map<int,int> nw=cur;
        nw[me[0]+me[1]]=me[0];
        int j=rec(tm+1,r,nw);
        if(j!=-1)
            return j;
    }
    lft[me[0]+me[1]]=me[1];
    for(auto &z : lft){
        if(z.f>me[0]+me[1])
            ++z.s;
    }
    if(!cur.count(me[0]+me[1]) || cur[me[0]+me[1]]<me[0]){
        return rec(l,tm-1,cur);
    }
    return -1;
}
int find_best(int n) {
    map<int,int> mp;
    return rec(0,n-1,mp);
}

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