Submission #499572

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

books

#include <bits/stdc++.h>
#include "books.h"
using namespace std;
//
// --- Sample implementation for the task books ---
//
// To compile this program with the sample grader, place:
//     books.h books_sample.cpp sample_grader.cpp
// in a single folder and run:
//     g++ books_sample.cpp sample_grader.cpp
// in this folder.
//

void solve(int N, int K, long long A, int S) {
    long long L = 1, R = N;
    long long omk = 0;
    while(L <= R) {
        long long mid = (L + R) >> 1;
        long long val = skim(mid);
        if(val <= A) {
            L = mid + 1;
            omk = mid;
        }
        else {
            R = mid - 1;
        }
    }
    //cout << "omk = " << omk << "\n";
    if(omk != N) {
        omk++;
    }
    if(omk <= K) {
        vector<int> val;
        int sum = 0;
        for(int i = 1; i <= K; i++) {
            int hii = skim(i);
            val.push_back(i);
            sum += hii;
        }
        if(sum > 2 * A || sum < A) {
            impossible();
        }
        else {
            answer(val);
        }
        return;
    }
    vector<pair<int, int> > val;
    set<int> hoho;
    for(int i = 1; i <= K; i++) {
        int value = skim(i);
        val.push_back({i, value});
        hoho.insert(i);
    }
    for(int i = omk; i > omk - K; i--) {
        if(!hoho.count(i)) {
            int value = skim(i);
            val.push_back({i, value});
            hoho.insert(i);
        }
    }
    vector<int> ans;
    int newn = val.size();
    int pref[newn], suf[newn];
    for(int i = 0; i < newn; i++) {
        pref[i] = 0;
        suf[i] = 0;
    }
    pref[0] = val[0].second;
    suf[newn - 1] = val[newn - 1].second;
    for(int i = 1; i < val.size(); i++) {
        pref[i] = pref[i - 1] + val[i].second;
    }
    for(int i = val.size() - 2; i >= 0; i--) {
        suf[i] = suf[i + 1] + val[i].second;
    }
    int cur_ans = 0;
    for(int i = newn - 1; i > newn - 1 - K; i--) {
        cur_ans += val[i].second;
    }
    if(cur_ans < A) {
        impossible();
        return;
    }
    if(cur_ans <= 2 * A) {
        for(int i = newn - K; i < newn; i++) {
            ans.push_back(val[i].first);
        }
        answer(ans);
        return;
    }
    int pos = newn - 1;
    for(int i = 1; i <= K; i++) {
        cur_ans -= val[pos--].second;
        cur_ans += val[i].second;
        if(cur_ans <= 2 * A) {
            assert(cur_ans >= A);
            for(int j = 1; j <= i; j++) {
                ans.push_back(val[j].first);
            }
            for(int j = newn - K; j <= pos; j++) {
                ans.push_back(val[j].first);
            }
            answer(ans);
            return;
        }
    }
    impossible();
}

Compilation message (stderr)

books.cpp: In function 'void solve(int, int, long long int, int)':
books.cpp:71:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for(int i = 1; i < val.size(); i++) {
      |                    ~~^~~~~~~~~~~~

• 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