Submission #918306

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

books

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

int a[MXN];

int val(int 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;
    }
    int l = 1, r = N + 1;
    while (l < r)
    {
        int mid = (l + r) >> 1;
        if (val(mid) >= A) r = mid;
        else l = mid + 1;
    }
    if (l < K)
    {
        impossible();
        return;
    }
    if (l < N + 1)
    {
        int res = 0;
        for (int 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;
        }
    }
    int m = l - 1;
    set<int> s;
    // min sub
    for (int i = 1; i <= K; i++) s.insert(i);
    // max sub
    for (int i = m - K + 1; i <= m; i++) s.insert(i);
    vector<int> arr;
    for (int x : s) arr.push_back(x);
    int res = 0;
    for (int i = 0; i < K; i++) res += val(arr[i]);
    for (int i = 0; i + K <= arr.size(); i++)
    {
        if (res >= A)
        {
            vector<int> v;
            for (int 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:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for (int i = 0; i + K <= arr.size(); i++)
      |                     ~~~~~~^~~~~~~~~~~~~
books.cpp:68:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         if (i + K == arr.size()) break;
      |             ~~~~~~^~~~~~~~~~~~~

• 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