Submission #440307

#	Time	Username	Problem	Language	Result	Execution time	Memory
440307		Ozy	A Difficult(y) Choice (BOI21_books)	C++17	100 / 100	2 ms	1052 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 a,n,k,s,prim,sum,p;
lli arr[MAX+2];
vector<int> res;
deque<int> cola;

lli binaria(lli lim) {
    lli ini,fin,mitad,ult;

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

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

        if (arr[mitad] >= lim) {
            ult = mitad;
            fin = mitad-1;
        }
        else ini = mitad+1;
    }

    return ult;
}

void cambia() {
    while (!cola.empty()) {
        res.push_back( cola.front());
        cola.pop_front();
    }
    sort(res.begin(), res.end());
}

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;
    arr[n+1] = (2*a)+1;

    prim = binaria(a);

    if (prim < k) {impossible(); return;}

    sum = arr[prim];
    repa(i,k-1,1) {
        if (arr[i] == -1) arr[i] = skim(i);
        sum += arr[i];
        cola.push_back(i);
    }

    if (sum <= (2*a) && sum >= a) {
        cola.push_back(prim);
        cambia();
        answer(res);
        return;
    }

    if (prim == k) {impossible(); return;}

    sum -= arr[prim];
    if (arr[k] == -1) arr[k] = skim(k);
    cola.push_front(k);
    sum += arr[k];
    if (sum > (2*a)) {impossible(); return;}

    repa(i,k,1) {

        if (sum >= a && sum <= (2*a)) break;

        sum -= arr[i];
        cola.pop_front();

        p = prim - (k - i + 1);
        if (arr[p] == -1) arr[p] = skim(p);

        sum += arr[p];
        cola.push_back(p);

        if (sum >= a && sum <= (2*a)) break;
    }

    if (sum < a) {impossible(); return;}

    cambia();
    answer(res);
}

Compilation message (stderr)

books.cpp: In function 'long long int binaria(long long int)':
books.cpp:34:12: warning: 'ult' may be used uninitialized in this function [-Wmaybe-uninitialized]
   34 |     return ult;
      |            ^~~

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