Submission #237898

#	Time	Username	Problem	Language	Result	Execution time	Memory
237898		lyc	The Big Prize (IOI17_prize)	C++14	90 / 100	121 ms	1400 KiB

prize

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

#define TRACE(x) cout << #x << " :: " << x << endl;
#define _ << " " <<

const int mxN = 2e5+5;
const int mxQ = 10000;
int n, q = 0;
map<int,vector<int>> cache;

vector<int> query(int i) {
    //TRACE("QUERY" _ i);
    assert(i >= 0 && i < n);
    if (cache.count(i)) return cache[i];
    assert(++q <= mxQ);
    return cache[i] = ask(i);
}

int find_best(int _n) {
    n = _n;
    int mxc = 0;
    for (int i = 0; i < min(n,473); ++i) {
        auto res = query(i);
        mxc = max(mxc,res[0]+res[1]);
    }
    for (int i = 0; i < n;) {
        auto res = query(i);
        int c = res[0]+res[1];
        if (c == 0) return i;
        if (c == mxc) {
            int lo = i, hi = n;
            while (hi-lo > 1) {
                int mid = (lo+hi)/2;
                auto y = query(mid);
                if (y[0] == res[0] && y[1] == res[1]) lo = mid;
                else hi = mid;
            }
            i = hi;
        } else ++i;
    }
    assert(false);
	return 0;
}

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