Submission #558209

#	Time	Username	Problem	Language	Result	Execution time	Memory
558209		cheissmart	A Difficult(y) Choice (BOI21_books)	C++14	100 / 100	2 ms	336 KiB

books

#include "books.h"
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7;

using namespace std;

map<int, ll> mp;

ll qry(int x) {
    if(mp.count(x) == 0) mp[x] = skim(x);
    return mp[x];
}

void solve(int n, int k, ll a, int s) {
    int lb = 1, rb = n;
    while(lb <= rb) {
        int mb = (lb + rb) / 2;
        if(qry(mb) >= a) rb = mb - 1;
        else lb = mb + 1;
    }
    if(lb <= n && lb >= k) {
        vi ans({lb});
        ll sum = qry(lb);
        assert(sum >= a);
        for(int i = 1; i < k; i++)
            sum += qry(i), ans.PB(i);
        if(sum <= 2 * a) {
            answer(ans);
            return;
        }
    }
    if(lb > k) {
        ll sum = 0;
        vi ans;
        for(int i = 1; i <= k; i++)
            sum += qry(i), ans.PB(i);
        if(sum <= 2 * a) {
            for(int j = 0; j < k && sum < a; j++) {
                sum -= qry(k - j);
                ans.erase(find(ALL(ans), k - j));
                sum += qry(lb - 1 - j);
                ans.PB(lb - 1 - j);
            }
            if(sum >= a) {
                assert(sum <= 2 * a);
                answer(ans);
                return;
            }
        }
    }
    impossible();
}

• 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