Submission #405302

#	Time	Username	Problem	Language	Result	Execution time	Memory
405302		temurbek_khujaev	The Big Prize (IOI17_prize)	C++17	0 / 100	90 ms	320 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;
        }
    }


}

const int k = 300;

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;
    SQ = sqrt(n);

    v = ask(n - 1);
    while (v[0] + v[1] < SQ) {
        if (v[0] + v[1] == 0) return n - 1;
        n--;
        v = ask(n - 1);
    }

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

    return 0;
}

Compilation message (stderr)

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

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