Submission #535432

#	Time	Username	Problem	Language	Result	Execution time	Memory
535432		mario05092929	The Big Prize (IOI17_prize)	C++14	100 / 100	77 ms	12132 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int INF = 1e9;
typedef long long ll;
typedef pair <int,int> pi;
typedef vector <int> vec;
using namespace std;
vector <int> g[435];
int di = 473,m,n,pmx,la,big;
vec d[200005];

vec getAsk(int x) {
    if(d[x][0] != -1) return d[x];
    return d[x] = ask(x);
}

int find_best(int N) {
    n = N; m = n/di+(n%di>0);
    for(int i = 0;i < n;i++) d[i].push_back(-1), d[i].push_back(-1);
    for(int i = 0;i < m;i++) {
        for(int j = i*di;j < min(n,i*di+di);j++) g[i].push_back(j);
    }
    int cn = 0;
    for(int i = 0;i < m&&cn < di;i++,cn++) {
        vec tmp = getAsk(g[i].back());
        pmx = max(pmx,tmp[0]+tmp[1]);
    }
    for(int i = 0;i < n&&cn < di;i++,cn++) {
        vec tmp = getAsk(i);
        pmx = max(pmx,tmp[0]+tmp[1]);
    }
    la = -1;
    for(int i = 0;i < m;) {
        //cout << i << ' ' << la << '\n';
        vec tmp = getAsk(g[i].back());
        if(la == g[i].back()) {
            i++; continue;
        }
        if(tmp[0]+tmp[1] == pmx&&tmp[0] == big) {
            i++; continue;
        }
        la = max(la+1,g[i][0]);
        int l = la,r = g[i].back();
        int wi = -1;
        while(l <= r) {
            int mid = (l + r) >> 1;
            vec t = getAsk(mid);
            if(t[0]+t[1] != pmx) wi = mid;
            if(t[0]+t[1] != pmx||t[0] != big) r = mid-1;
            else l = mid+1;
        }
        if(wi == -1) while(1);
        vec t2 = getAsk(wi);
        if(t2[0]+t2[1] == pmx) while(1);
        if(t2[0]+t2[1] == 0) return wi;
        la = wi;
        big++;
    }
    return -1;
}

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