Submission #789105

#	Time	Username	Problem	Language	Result	Execution time	Memory
789105		t6twotwo	The Big Prize (IOI17_prize)	C++17	94.49 / 100	53 ms	11392 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> memo;
vector<int> K(int i) {
	if(memo[i][0] != -1) return memo[i];
	return ask(i);
}
int find_best(int N) {
    memo.resize(N, {-1, -1});
    int lol = -1, ted = -1, cnt = 0;
    vector<vector<int>> a(472);
    for (int i = 0; i < 472; i++) {
        a[i] = K(i);
        int s = a[i][0] + a[i][1];
        if (s == 0) {
            return i;
        }
        lol = max(lol, s);
    }
    for (int i = 0; i < 472; i++) {
        int s = a[i][0] + a[i][1];
        if (s < lol) {
            cnt++;
            ted = max(ted, s);
        }
    }
    int x = 472;
    while (cnt < 25) {
        vector<int> t = K(x);
        int s = t[0] + t[1];
        if (s == 0) {
            return x;
        }
        if (s == lol) {
            int lo = x, hi = N - 1;
            while (lo < hi) {
                int mi = (lo + hi + 1) / 2;
                vector<int> v = K(mi);
                if (v == t) {
                    lo = mi;
                } else {
                    hi = mi - 1;
                }
            }
            x = lo;
        } else {
            cnt++;
            ted = max(ted, s);
        }
        x++;
    }
    while (1) {
        vector<int> t = K(x);
        int s = t[0] + t[1];
        if (s == 0) {
            return x;
        }
        if (s < ted) {
            x++;
            continue;
        }
        if (s == lol) {
            int lo = x, hi = N - 1;
            while (lo < hi) {
                int mi = (lo + hi + 1) / 2;
                vector<int> v = K(mi);
                if (v == t) {
                    lo = mi;
                } else {
                    hi = mi - 1;
                }
            }
            x = lo + 1;
        } else {
            int lo = x, hi = N - 1;
            while (lo < hi) {
                int mi = (lo + hi + 1) / 2;
                vector<int> v = K(mi);
                if (v == t) {
                    lo = mi;
                } else if (v[0] + v[1] == lol) {
                    int l = lo + 1, r = mi;
                    while (l < r) {
                        int m = (l + r) / 2;
                        vector<int> u = K(m);
                        if (u == v) {
                            r = m;
                        } else {
                            l = m + 1;
                        }
                    }
                    if (K(l - 1) == t) {
                        lo = mi;
                    } else {
                        hi = l - 2;
                    }
                } else {
                    hi = mi - 1;
                }
            }
            x = lo + 1;
        }
    }
}

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