Submission #789127

#	Time	Username	Problem	Language	Result	Execution time	Memory
789127		t6twotwo	The Big Prize (IOI17_prize)	C++17	20 / 100	92 ms	11332 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, ono = 0;
    vector<int> chuchu;
    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++;
            if (s > ted) {
                ted = s;
                ono = 0;
                chuchu = a[i];
            } else if (s < ted) {
                ono++;
            }
        }
    }
    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++;
            if (s > ted) {
                ted = s;
                ono = 0;
                chuchu = t;
            } else if (s < ted) {
                ono++;
            }
        }
        x++;
    }
    while (1) {
        vector<int> t = K(x);
        int s = t[0] + t[1];
        if (s == 0) {
            return x;
        }
        if (s < ted) {
            x++;
            ono++;
            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[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 (chuchu[0] + ono == K(l - 1)[0]) {
                        lo = mi;
                    } else {
                        hi = mi - 1;
                    }
                } else {
                    if (chuchu[0] + ono == v[0]) {
                        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;
                    bool f = 0;
                    while (l < r) {
                        int m = (l + r) / 2;
                        vector<int> u = K(m);
                        if (u[0] + u[1] == lol) {
                            if (u == v) {
                                r = m;
                            } else {
                                l = m + 1;
                            }
                        } else if (u[0] + u[1] == ted) {
                            if (t == u) {
                                lo = m;
                                l = m + 1;
                            } else {
                                f = 1;
                                hi = m - 1;
                                break;
                            }
                        } else {
                            f = 1;
                            hi = m - 1;
                            break;
                        }
                    }
                    if (!f) {
                        if (K(l - 1) == t) {
                            lo = mi;
                        } else {
                            hi = l - 2;
                        }
                    }
                } else {
                    hi = mi - 1;
                }
            }
            x = lo + 1;
        }
    }
}

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