Submission #1322023

#	Time	Username	Problem	Language	Result	Execution time	Memory
1322023		kasamchi	The Big Prize (IOI17_prize)	C++20	97.67 / 100	20 ms	5268 KiB

prize

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

vector<vector<int>> buf;

vector<int> qry(int x) {
    if (buf[x].empty()) {
        buf[x] = ask(x);
    }
    return buf[x];
}

int find_best(int n) {
    buf.clear(), buf.resize(n);

    vector<int> s(6);
    for (int i = 0; i < min(n, 474); i++) {
        vector<int> res = qry(i);
        s[5] = max(s[5], res[0] + res[1]);
    }

    vector<int> pidx;
    for (int i = 1; i <= s[5]; i++) {
        int l = -1, r = n - 1;
        while (l + 1 < r) {
            int rm = l + (r - l) / 2, lm = rm;
            vector<int> res = qry(lm);
            while (res[0] + res[1] != s[5]) {
                lm--;
                if (lm < 0) {
                    break;
                }
                res = qry(lm);
            }
            if (lm < 0) {
                if (rm + 1 < i) {
                    l = rm;
                } else {
                    r = rm;
                }
            } else {
                if (res[0] + rm - lm < i) {
                    l = rm;
                } else {
                    r = rm;
                }
            }
        }
        pidx.push_back(r);
    }

    for (int x : pidx) {
        vector<int> res = qry(x);
        if (res[0] + res[1] == 0) {
            return x;
        }
    }
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:59:1: warning: control reaches end of non-void function [-Wreturn-type]
   59 | }
      | ^

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