Submission #311699

#	Time	Username	Problem	Language	Result	Execution time	Memory
311699		semiauto	The Big Prize (IOI17_prize)	C++11	93.98 / 100	61 ms	5496 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
int i,s=1,pos,l,r;
vector <int> v[200001];
set <pair <int,int> > myset;
int find_best(int n) {
    v[1]=ask(1);
    for (i=1;i<=475;i++) {
        v[i]=ask(i-1);
        if ((v[i][0]+v[i][1])==0)
            return i-1;
        if ((v[s][0]+v[s][1])<=(v[i][0]+v[i][1]))
            s=i;
    }

    for (i=n;i>0;i--) {
        if (!(v[i].size()))
            v[i]=ask(i-1);
        if ((v[i][0]+v[i][1])==0)
            return i-1;
        if ((v[s][0]+v[s][1])==(v[i][0]+v[i][1]))
            break;
    }

    myset.insert({v[s][0],s});
    myset.insert({v[i][0],i});

    while (true){

        pos=s;
        l=(*(--(myset.upper_bound({v[s][0],200001})))).second;
        r=(*(myset.upper_bound({v[s][0]+1,0}))).second;

        for (i=17;i>=0;i--) {
            if (pos+(1<<i)>=r)
                continue;
            pos+=(1<<i);
            if (pos<=l)
                continue;
            if (!(v[pos].size()))
                v[pos]=ask(pos-1);
            if ((v[pos][0]+v[pos][1])!=(v[s][0]+v[s][1])) {
                if ((v[pos][0]+v[pos][1])==0)
                    return pos-1;
                pos-=(1<<i);
                continue;
            }

            myset.insert({v[pos][0],pos});
            if (v[pos][0]>v[s][0])
                pos-=(1<<i);
        }

        for (i=pos+1;i<=n;i++) {
            if (!(v[i].size()))
                v[i]=ask(i-1);
            if ((v[i][0]+v[i][1])==0)
                return i-1;
            if ((v[i][0]+v[i][1])==(v[s][0]+v[s][1]))
                break;
        }

        s=i;
        myset.insert({v[s][0],s});

    }
}

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