Submission #405003

#	Time	Username	Problem	Language	Result	Execution time	Memory
405003		nicolaalexandra	A Difficult(y) Choice (BOI21_books)	C++14	100 / 100	3 ms	344 KiB

books

#include<bits/stdc++.h>

#include"books.h"
#define DIM 100010
using namespace std;
int n,k,s,i;
long long a;
long long v[DIM],d[DIM];
void solve(int n, int k, long long a, int s) {
    int i;

    long long sum = 0;
    for (i=1;i<=k;i++){
        d[i] = skim(i);
        sum += d[i];
    }

    if (sum > 2*a){
        impossible();
        return;
    }

    vector <int> ans;
    if (sum >= a){
        for (i=1;i<=k;i++)
            ans.push_back(i);
        answer(ans);
        return;
    }

    sum -= d[k];
    int st = k, dr = n, poz = n+1;
    long long val;

    while (st <= dr){
        int mid = (st + dr) >> 1;
        long long nr = skim (mid);
        d[mid] = nr;
        if (nr >= a){
            poz = mid, val = nr;
            dr = mid-1;
        } else st = mid+1;

    }

    if (poz <= n && sum + val >= a && sum + val <= 2*a){

        ans.push_back(poz);
        for (i=1;i<k;i++)
            ans.push_back(i);


    } else {

        sum += d[k];
        int st = 1, dr = poz - k;

        while (dr <= n && sum < a){
            sum -= d[st];
            if (!d[dr])
                d[dr] = skim(dr);
            sum += d[dr];
            st++, dr++;
        }

        if (sum < a || sum > 2*a){
            impossible();
            return;
        }

        for (i=st;i<=k;i++)
            ans.push_back(i);
        for (i=poz-k;i<dr;i++)
            ans.push_back(i);
    }

    sort (ans.begin(),ans.end());
    answer(ans);


}

Compilation message (stderr)

books.cpp: In function 'void solve(int, int, long long int, int)':
books.cpp:46:25: warning: 'val' may be used uninitialized in this function [-Wmaybe-uninitialized]
   46 |     if (poz <= n && sum + val >= a && sum + val <= 2*a){
      |                     ~~~~^~~~~

• 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