Submission #222752

#	Time	Username	Problem	Language	Result	Execution time	Memory
222752		achibasadzishvili	The Big Prize (IOI17_prize)	C++14	90 / 100	85 ms	2744 KiB

prize

#include<bits/stdc++.h>
#define ll int
#define f first
#define s second
#define pb push_back
#include "prize.h"
using namespace std;
pair<ll,ll>p , cur , pp[200005];
ll que,fix[200005] , mx , tt = 0;
set<ll>st;
set<ll>::iterator it;
pair<ll,ll> as(ll ind){
    if(fix[ind])return pp[ind];
    fix[ind] = 1;
    vector<ll>v = ask(ind);
    que++;
    pp[ind] = make_pair(v[0] , v[1]);
    if(v[0] + v[1] != mx && tt == 1){
        st.insert(ind);
    }
    return pp[ind];
}
ll find_best(ll n){
    srand(time(NULL));
    ll ind = 0; mx = 0;
    vector<ll>ff;
    for(int i=1; i<=500; i++){
        ll t = rand() % n;
        p = as(t);
        ff.pb(t);
        if(p.f + p.s > mx){
            mx = p.f + p.s;
            ind = t;
        }
    }
    tt = 1;
    ll x = ind;
    st.insert(0);
    st.insert(n - 1);
    for(int i=0; i<ff.size(); i++)
        if(pp[ff[i]].f + pp[ff[i]].s != mx)
            st.insert(ff[i]);
    while(x < n){
        p = as(x);
        cur = p;
        if(p.f + p.s == mx){
            ll l = x + 1 , r = n - 1 , mid , nex = x;
            if(st.upper_bound(x) != st.end())
                r = (*st.upper_bound(x));
            while(r >= l){
                mid = (l + r) / 2;
                p = as(mid);
                if(p.s == cur.s){
                    l = mid + 1;
                    nex = mid;
                }
                else {
                    r = mid - 1;
                }
            }
            x = nex + 1;
        }
        else {
            if(p.f + p.s == 0)return x;
            x++;
        }
    }
    
    x = ind;
    
    while(x >= 0){
        p = as(x);
        cur = p;
        if(p.f + p.s == mx){
            it = st.lower_bound(x);
            it--;
            ll l = (*it) , r = x - 1 , mid , nex = x;
            while(r >= l){
                mid = (l + r) / 2;
                p = as(mid);
                if(p.f == cur.f){
                    r = mid - 1;
                    nex = mid;
                }
                else {
                    l = mid + 1;
                }
            }
            x = nex - 1;
        }
        else {
            if(p.f + p.s == 0)return x;
            x--;
        }
    }
    
	return 0;
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:40:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<ff.size(); i++)
                  ~^~~~~~~~~~

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