Submission #1322014

#	Time	Username	Problem	Language	Result	Execution time	Memory
1322014		kasamchi	The Big Prize (IOI17_prize)	C++20	20 / 100	26 ms	404 KiB

prize

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

int find_best(int n) {
    vector<int> s(6);
    for (int i = 0; i < min(n, 474); i++) {
        vector<int> res = ask(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 = ask(lm);
            while (res[0] + res[1] != s[5]) {
                lm--;
                if (lm < 0) {
                    break;
                }
                res = ask(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 = ask(x);
        if (res[0] + res[1] == 0) {
            return x;
        }
    }
}

Compilation message (stderr)

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

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