Submission #918309

#	Time	Username	Problem	Language	Result	Execution time	Memory
918309		aykhn	A Difficult(y) Choice (BOI21_books)	C++17	100 / 100	1 ms	760 KiB

books

#include <bits/stdc++.h>
#include "books.h"
using namespace std;
const int MXN = 1e5 + 5;

long long a[MXN];

long long val(long long i)
{
    return !a[i] ? a[i] = skim(i) : a[i];
}

void solve(int N, int K, long long A, int S) 
{
    if (K > N)
    {
        impossible();
        return;
    }
    long long l = 1, r = N + 1;
    while (l < r)
    {
        long long mid = (l + r) >> 1;
        if (val(mid) >= A) r = mid;
        else l = mid + 1;
    }
    if (l < K)
    {
        impossible();
        return;
    }
    if (l < N + 1)
    {
        long long res = 0;
        for (long long i = 1; i < K; i++)
        {
            res += val(i);
        }
        res += val(l);
        if (A <= res && res <= 2*A)
        {
            vector<int> v(K - 1);
            iota(v.begin(), v.end(), 1);
            v.push_back(l);
            answer(v);
            return;
        }
    }
    long long m = l - 1;
    set<long long> s;
    // min sub
    for (long long i = 1; i <= K; i++) s.insert(i);
    // max sub
    for (long long i = m - K + 1; i <= m; i++) s.insert(i);
    vector<long long> arr;
    for (long long x : s) arr.push_back(x);
    long long res = 0;
    for (long long i = 0; i < K; i++) res += val(arr[i]);
    for (long long i = 0; i + K <= arr.size(); i++)
    {
        if (res >= A)
        {
            vector<int> v;
            for (long long j = i; j < i + K; j++) v.push_back(arr[j]);
            answer(v);
            return;
        }
        if (i + K == arr.size()) break;
        res -= val(arr[i]);
        res += val(arr[i + K]);
    }
    impossible();
}

Compilation message (stderr)

books.cpp: In function 'void solve(int, int, long long int, int)':
books.cpp:59:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for (long long i = 0; i + K <= arr.size(); i++)
      |                           ~~~~~~^~~~~~~~~~~~~
books.cpp:68:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         if (i + K == arr.size()) break;
      |             ~~~~~~^~~~~~~~~~~~~

• 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