Submission #660319

#	Time	Username	Problem	Language	Result	Execution time	Memory
660319		urosk	The Big Prize (IOI17_prize)	C++14	90 / 100	103 ms	6472 KiB

prize

#include "prize.h"
#define dbg(x) cerr<<#x<<": "<<x<<endl
#define here cerr<<"================================\n"
#include <bits/stdc++.h>
#define ll int
#define llinf 1000000000
#define pb push_back
#define sz(a) (ll)(a.size())
#define all(a) a.begin(),a.end()
#define fi first
#define sc second

using namespace std;
#define maxn 200005
vector<ll> cnt(2);
vector<ll> c[maxn];
bool ima[maxn];
ll val[maxn];
void calc(ll i){
    if(ima[i]) return;
    ima[i] = 1;
    c[i] = ask(i-1);
    val[i] = c[i][0] + c[i][1];
    return;
}
ll find_best(ll n) {
    ll d = 1;
    while(d*d<n) d++;
    d = min(3*d,n);
    ll mn = llinf,mx = 0;
    set<ll> nxt;
    for(ll i = 1;i<=d;i++){
        calc(i);
        mx = max(val[i],mx);
    }
    for(ll i = 1;i<=d;i++){
        if(val[i]!=mx) nxt.insert(i);
    }
    ll i = d;
    while(val[i]!=mx){
        if(i!=d) nxt.insert(i);
        i++;
        calc(i);
    }
    ll l = i+1,r = n;
    calc(r);
    while(val[r]!=mx&&r>l){
        nxt.insert(r);
        r--;
        calc(r);
    }
    ll rn = r,mid;
    while(l<rn){
        r = rn;
        calc(l);
        if(c[l][0]==c[r][0]) break;
        ll poc = c[l][0];
        l++;
        r--;
        while(l<=r){
            mid = (l+r)/2;
            calc(mid);
            bool f = 0;
            while(val[mid]!=mx&&mid>=l){
                mid--;
                calc(mid);
                f = 1;
            }
            if(c[mid][0]==poc){
                if(f){
                    for(ll j = mid+1;j<=(l+r)/2;j++) nxt.insert(j);
                    break;
                }
                l = mid+1;
            }else r = mid-1;
        }
        auto it = nxt.end(); it--; l = *it + 1;
        while(val[l]!=mx&&l<rn){
            nxt.insert(l);
            l++;
            calc(l);
        }
    }
    ll ans = 0;
    for(ll i : nxt){
        calc(i);
        if(val[i]==0) ans = i;
    }
    return ans-1;
}
/*
8
3 2 3 1 3 3 2 3
*/

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:30:8: warning: unused variable 'mn' [-Wunused-variable]
   30 |     ll mn = llinf,mx = 0;
      |        ^~

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