Submission #283722

#	Time	Username	Problem	Language	Result	Execution time	Memory
283722		ToMmyDong	The Big Prize (IOI17_prize)	C++11	90 / 100	119 ms	1300 KiB

prize

#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define SZ(i) int(i.size())
#define ALL(i) i.begin(), i.end()
#define MEM(i,a) memset(i, (a), sizeof(i))
#define X first
#define Y second
#define eb emplace_back
#define pb push_back
#ifdef tmd
#define debug(...) fprintf(stderr,"#%d-(%s)=",__LINE__,#__VA_ARGS__);_do(__VA_ARGS__);
template<typename T> void _do (T &&x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y) {cerr<<x<<", ";_do(y...);}
#else
#define debug(...)
#endif


map<int, vector<int> > mem;
vector<int> sask (int idx) {
    if (mem.count(idx) == 0) {
        mem[idx] = ask(idx);
    }
    return mem[idx];
}

int find_best(int n) {

    srand(880301);
    int mx = 0;
    for (int i=0; i<50; i++) {
        vector<int> res = sask(rand() % n);
        mx = max(mx, res[0] + res[1]);
    }
    debug(mx);
	for(int i = 0; i < n; i++) {
		std::vector<int> res = sask(i);
		if(res[0] + res[1] == 0) return i;
        if (res[0] + res[1] < mx) continue;
        int L = i, R = n;
        while (L < R - 1) {
            int M = (L + R) >> 1;
            vector<int> resM = sask(M);
            if (resM[0] + resM[1] == 0) return M;
            if (resM == res) {
                L = M;
            } else {
                R = M;
            }
        }
        debug(i, R);
        i = R-1;
	}
	return 0;
}

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