Submission #222750

#	Time	Username	Problem	Language	Result	Execution time	Memory
222750		achibasadzishvili	The Big Prize (IOI17_prize)	C++14	20 / 100	87 ms	2808 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];
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]);
    return pp[ind];
}
ll find_best(ll n){
    srand(time(NULL));
    ll ind = 0 , mx = 0;
    for(int i=1; i<=100; i++){
        ll t = rand() % n;
        p = as(t);
        if(p.f + p.s > mx){
            mx = p.f + p.s;
            ind = t;
        }
    }
    ll x = ind;
    
    while(x < n){
        p = as(x);
        cur = p;
        if(p.f + p.s == mx){
            ll l = x + 1 , r = n - 1 , mid , nex = 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){
            ll l = 0 , 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;
}

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