Submission #405331

#	Time	Username	Problem	Language	Result	Execution time	Memory
405331		temurbek_khujaev	The Big Prize (IOI17_prize)	C++17	95.89 / 100	67 ms	400 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>

using namespace std;
int SQ;

int first_small(int l, int r, int ls, int rs) {

    while (l <= r) {
        int m = (l + r) >> 1;
        vector<int> v = ask(m);
        if (v[0] + v[1] < SQ) {
            r = m;
            if (l == r) {
                if (v[0] + v[1] == 0) return -m;
                else return m;
            }
        } else {
            if (v[0] > ls) r = m - 1;
            else {
                l = m + 1;
            }

        }
    }
//    if (pos != -1) pos = 1 / 0;


}

const int k = 280;

int small_solution(int n) {
    for (int i = 0; i < n; i++) {
        vector<int> v = ask(i);
        if (v[0] + v[1] == 0) return i;
    }
}

int find_best(int n) {
    if (n < 5000) return small_solution(n);


    vector<int> v = ask(0);
    if (v[0] + v[1] == 0) return 0;
    SQ = 1;
    set<int> s = {0};
    for (int i = 0; i < 450; i++) {
        int x = rand() % n;
        while (s.count(x)) x = rand() % n;
        s.insert(x);
        v = ask(x);
        if (v[0] + v[1] == 0) return x;
        SQ = max(SQ, v[0] + v[1]);
    }
    cerr << "SQ = " << SQ << endl;
    v = ask(n - 1);
    while (v[0] + v[1] < SQ) {
        if (v[0] + v[1] == 0) return n - 1;
        n--;
        v = ask(n - 1);
    }
    cerr << "new n = " << n << endl;
    int i = min(n - 1, k);
    int lc = 0;
    int j = 0;
    while (true) {
        v = ask(i);

        while (v[0] + v[1] < SQ) {
            if (v[0] + v[1] == 0) return i;
            v = ask(++i);
        }
        int rc = v[1];
        int cnt = v[0] - lc;
        while (cnt--) {
            int p = first_small(j, i - 1, lc, rc);
            if (p < 0) return -p;
            j = p + 1;
            lc++;
        }
        lc = v[0];
        j = i + 1;
        if (i == n - 1) break;
        i = min(i + k, n - 1);
    }

    return -1;
}

Compilation message (stderr)

prize.cpp: In function 'int first_small(int, int, int, int)':
prize.cpp:29:1: warning: control reaches end of non-void function [-Wreturn-type]
   29 | }
      | ^
prize.cpp: In function 'int small_solution(int)':
prize.cpp:38:1: warning: control reaches end of non-void function [-Wreturn-type]
   38 | }
      | ^

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