Submission #222749

#	Time	Username	Problem	Language	Result	Execution time	Memory
222749		achibasadzishvili	The Big Prize (IOI17_prize)	C++14	20 / 100	84 ms	512 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;
ll que;
pair<ll,ll> as(ll ind){
    vector<ll>v = ask(ind);
    que++;
    if(que > 10000){
        while(true);
    }
    return make_pair(v[0] , v[1]);
}
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