Submission #789109

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
789109	2023-07-21T04:59:25 Z	t6twotwo	The Big Prize (IOI17_prize)	C++17	20 / 100	56 ms	11328 KB

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;
                    bool f = 0;
                    while (l < r) {
                        int m = (l + r) / 2;
                        vector<int> u = K(m);
                        if (u == v) {
                            r = m;
                        } 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.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	11172 KB	Output is correct
2	Correct	11 ms	11168 KB	Output is correct
3	Correct	12 ms	11148 KB	Output is correct
4	Correct	11 ms	11300 KB	Output is correct
5	Correct	13 ms	11172 KB	Output is correct
6	Correct	12 ms	11216 KB	Output is correct
7	Correct	15 ms	11216 KB	Output is correct
8	Correct	13 ms	11276 KB	Output is correct
9	Correct	11 ms	11328 KB	Output is correct
10	Correct	12 ms	11292 KB	Output is correct

Subtask #2

0 / 80.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	11152 KB	Output is correct
2	Correct	11 ms	11296 KB	Output is correct
3	Correct	18 ms	11172 KB	Output is correct
4	Correct	16 ms	11280 KB	Output is correct
5	Correct	15 ms	11272 KB	Output is correct
6	Correct	9 ms	11216 KB	Output is correct
7	Correct	13 ms	11204 KB	Output is correct
8	Correct	13 ms	11172 KB	Output is correct
9	Correct	13 ms	11216 KB	Output is correct
10	Correct	12 ms	11216 KB	Output is correct
11	Correct	11 ms	11288 KB	Output is correct
12	Correct	14 ms	11268 KB	Output is correct
13	Correct	15 ms	11172 KB	Output is correct
14	Correct	7 ms	1488 KB	Output is correct
15	Correct	19 ms	11280 KB	Output is correct
16	Incorrect	56 ms	11180 KB	Incorrect
17	Halted	0 ms	0 KB	-