Submission #1186598

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186598		YassirSalama	A Difficult(y) Choice (BOI21_books)	C++20	0 / 100	3 ms	1984 KiB

books

#include <bits/stdc++.h>
using namespace std;

#include "books.h"
#ifdef IOI
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }

void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__);
#else
#define dbg(...) 1337;
#endif

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.

/*
skim(index) : 1-indexed
answer(subset) : 1-indexed
impossible()
*/
//

void solve(int n, int k, long long a, int sss) {
    vector<__int128_t> v(n+1);
    for(int i=1;i<=n;i++){
        v[i] = skim(i);
    }
    set<int> s;
    __int128_t ss = 0;
    int i = 1;
    while(i <= n){
        // 1) if we're already good, answer immediately
        if (s.size()==k && ss>=a && ss<=2*a) {
            return answer(vector<int>(s.begin(), s.end()));
        }

        // 2) still filling up
        if (s.size() < k){
            ss += v[i];
            s.insert(i);
            ++i;
            continue;
        }

        // 3) s.size()==k: try both evictions BEFORE mutating
        int js = *s.begin();               // index of smallest value
        int jl = *s.rbegin();              // index of largest value

        // try removing smallest or largest
        for(int j : {js, jl}) {
            __int128_t cand = ss - v[j] + v[i];
            if (cand >= a && cand <= 2*a) {
                // build the answer
                auto ans = vector<int>(s.begin(), s.end());
                ans.erase(find(ans.begin(), ans.end(), j));
                ans.push_back(i);
                return answer(ans);
            }
        }

        // 4) no immediate solution, decide whether to slide or skip
        __int128_t S_small = ss - v[js] + v[i];
        if (S_small < a) {
            // even the smallest-eviction didn't reach A, so we evict the smallest:
            s.erase(js);
            ss = S_small;
            s.insert(i);
        }
        // else S_small > 2*a ⇒ even the best eviction overshoots ⇒ skip i
        ++i;
    }

    // final check
    if (s.size()==k && ss>=a && ss<=2*a)
        return answer(vector<int>(s.begin(), s.end()));

    return impossible();
    // if(s.size()==k&&ss>=a&&ss<=2*a){
    //     return answer(vector<int>(s.begin(),s.end()));
    // }
    // return impossible();
}

• 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