Submission #715486

#	Time	Username	Problem	Language	Result	Execution time	Memory
715486		lmqzzz	The Big Prize (IOI17_prize)	C++14	97.41 / 100	57 ms	412 KiB

prize

#include "prize.h"

#include <bits/stdc++.h>
using namespace std;
int lolipop = -1;
int best = -1;
int solve(int l, int r, int before_left, int cnt) {
        if (cnt == 0) return -1;
        // cerr << l << ' ' << r << ' ' << before_left << '\n';
        if (l >= r) return -1;
        //[l, r)
        int m = l + r >> 1;
        // [l, m) [m + 1, r)
        int rm = m;
        int L, R;
        while (rm < r) {
                auto mid = ask(rm);
                if (mid[0] + mid[1] == 0) return rm;
                if (mid[0] + mid[1] == best) {
                        L = mid[0], R = mid[1];
                        break;
                }
                rm++;
        }
        int cnt_m = rm - m;
        int left_size = L - before_left - cnt_m;
        int right_size = cnt - left_size;
        if (rm == r) {
                return solve(l, m, before_left, left_size);
        } else {
                return max(solve(l, m, before_left, left_size), solve(rm + 1, r, L, right_size));
        }
}

int find_best(int n) {
        const int LIM = 500;
        vector<vector<int>> b(LIM);
        for (int i = 0; i < LIM; i++) {
                b[i] = ask(i);
                if (best < b[i][0] + b[i][1]) {
                        best = b[i][0] + b[i][1];
                        lolipop = i;
                }
                if (b[i][0] + b[i][1] == 0) return i;
        }
        int cnt = 0;
        for (int i = 0; i < LIM; i++) {
                if (b[i][0] + b[i][1] < best) cnt++;
        }
        return solve(LIM, n, cnt, best - cnt);
}

Compilation message (stderr)

prize.cpp: In function 'int solve(int, int, int, int)':
prize.cpp:12:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   12 |         int m = l + r >> 1;
      |                 ~~^~~
prize.cpp:15:16: warning: variable 'R' set but not used [-Wunused-but-set-variable]
   15 |         int L, R;
      |                ^
prize.cpp:26:27: warning: 'L' may be used uninitialized in this function [-Wmaybe-uninitialized]
   26 |         int left_size = L - before_left - cnt_m;
      |                         ~~^~~~~~~~~~~~~

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