Submission #439791

#	Time	Username	Problem	Language	Result	Execution time	Memory
439791		Ozy	A Difficult(y) Choice (BOI21_books)	C++17	45 / 100	2 ms	1180 KiB

books

#include <bits/stdc++.h>
#include "books.h"
using namespace std;
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define lli long long
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "

#define MAX 100000

lli l,r,n,a,s,k,falt;
lli arr[MAX+2],activos[MAX+2];
vector<int> res;

lli binaria(lli lim, bool tipo) {
    lli ult,ini,fin,mitad,p;
    ini = 0;
    fin = n;

    while (ini <= fin) {
        mitad = (ini+fin)/2;

        if (arr[mitad] == -1) arr[mitad] = skim(mitad);
        p = arr[mitad];

        if (!tipo && p <= lim) {
            ult = mitad;
            ini = mitad+1;
        }
        else if (tipo && p < lim) {
            ult = mitad;
            ini = mitad+1;
        }
        else fin = mitad-1;
    }
    if (tipo) ult++;

    return ult;
}

void solve(int N, int K, long long A, int S) {

    a = A;
    n = N;
    k = K;
    s = S;
    rep(i,1,n) arr[i] = -1;

    l = a/k;
    l = binaria(l,true);

    r = (2*a)/k;
    r = binaria(r,false);



    if ((r-l+1) >= k) {
        res.resize(k,0);
        rep(i,0,k-1) res[i] = l+i;
        answer(res);
    }
    else {

        falt = k - (r-l+1);

        lli sum = 0;
        l = max(1ll,l-falt);
        r = min(n,r+falt);

        rep(i,l,r) if (arr[i] == -1) arr[i] = skim(i);

        rep(i,0,k-1) {
            sum += arr[i+l];
            activos[i+l] = 1;
        }

        lli nuevo = l+k;
        while (sum < a && nuevo <= r) {
            sum += arr[nuevo];
            activos[nuevo++] = 1;
            rep(i,l,nuevo-1) {
                if (activos[i] == 0) continue;
                if (sum-arr[i] <= (2*a)) {
                    sum -= arr[i];
                    activos[i] = 0;
                    break;
                }
            }

        }

        if (sum >= a && sum <= (2*a)) {
            rep(i,l,r) if (activos[i] == 1) res.push_back(i);
            answer(res);
        }
        else impossible();

    }
}

Compilation message (stderr)

books.cpp: In function 'long long int binaria(long long int, bool)':
books.cpp:37:18: warning: 'ult' may be used uninitialized in this function [-Wmaybe-uninitialized]
   37 |     if (tipo) ult++;
      |               ~~~^~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 15
• Subtask 3: 10 / 10
• Subtask 4: 15 / 15
• Subtask 5: 0 / 15
• Subtask 6: 20 / 20
• Subtask 7: 0 / 20