Submission #414607

#	Time	Username	Problem	Language	Result	Execution time	Memory
414607		Victor	A Difficult(y) Choice (BOI21_books)	C++17	0 / 100	2 ms	968 KiB

books

#include "books.h"

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = a; i < b; ++i)
#define per(i, a, b) for (int i = b - 1; i >= a; --i)
#define trav(a, x) for (auto& a : x)
#define sz(a) a.size()
typedef pair<int, int> ii;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ii> vii;

void solve(int n, int k, ll a, int s) {
    ll vals[100001], val;
    int lo = 1, hi = n;

    while (lo != hi) {
        int mid = (hi + lo) >> 1;
        val = vals[mid];
        val = skim(mid);
        if (val < a)
            lo = mid + 1;
        else
            hi = mid;
    }

    memset(vals, 0, sizeof(vals));
    vals[lo] = val;

    ll taken = 0, sum = 0;
    rep(i, 1, k + 1) vals[i] = skim(i), sum += vals[i];
    rep(i, max(1, lo - k - 1), lo) vals[i] = skim(i);

    vi ans;
    int x = k - 1;
    rep(i, 0, x) sum += vals[i];

    per(i, 1, n + 1) {
        if (!vals[i]) continue;

        if (taken + vals[i] + sum <= 2 * a) {
            taken += vals[i];
            if (x) sum -= vals[--x];
            ans.push_back(i + 1);
        }

        if (i < x || sz(ans) == k) break;
    }

    if (ans.size() == k && a <= taken && taken <= 2 * a) answer(ans);
    impossible();
}

Compilation message (stderr)

books.cpp: In function 'void solve(int, int, ll, int)':
books.cpp:48:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   48 |         if (i < x || sz(ans) == k) break;
      |                              ^
books.cpp:51:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   51 |     if (ans.size() == k && a <= taken && taken <= 2 * a) answer(ans);
      |         ~~~~~~~~~~~^~~~
books.cpp:29:14: warning: 'val' may be used uninitialized in this function [-Wmaybe-uninitialized]
   29 |     vals[lo] = val;
      |     ~~~~~~~~~^~~~~

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