Submission #347197

#	Time	Username	Problem	Language	Result	Execution time	Memory
347197		jamezzz	The Big Prize (IOI17_prize)	C++14	90 / 100	106 ms	2048 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb emplace_back
#define ll long long
#define INF 1023456789
#define INFll 1023456789123456789
#define all(x) x.begin(), x.end()
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;

ii memo[200005];

ii query(int x){
    if (memo[x].fi == -1){
        auto t = ask(x);
        memo[x] = ii(t[0], t[1]);
    }
    return memo[x];
}

int find_best(int n) {
    for (int i = 0; i < n; ++i) memo[i] = ii(-1, -1);
    /*
    if (n <= 5000){
        for (int i = 0; i < n; ++i){
            ii t = query(i);
            if (t.fi + t.se == 0) return i;
        }
    }*/
    int x = 0;
	for(int i = 0; i < min(n - 1, 500); i++) {
        int p = (n / min(n - 1, 500)) * i;
        ii t = query(p);
        x = max(x, t.fi + t.se);
	}
    for (int i = 0; i < n; ++i){
        ii t = query(i);
        if (t.fi + t.se == 0) return i;
        else if (t.fi + t.se != x) continue;
        else{
            int r = t.se;
            int lo = i, hi = n - 1, mid, res = n - 1;
            while (lo <= hi){
                mid = (lo + hi) / 2;
                t = query(mid);
                if (t.fi + t.se != x) hi = mid - 1;
                else if (t.se != r) hi = mid - 1;
                else{
                    res = mid; lo = mid + 1;
                }
            }
            i = res;
        }
    }
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:60:1: warning: control reaches end of non-void function [-Wreturn-type]
   60 | }
      | ^

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