Submission #1240903

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

books

#include <bits/stdc++.h>

#include "books.h"

#define tiii tuple<int,int,int>
#define int long long

using namespace std;

vector<int> arr;

struct cmp{
    int ind;
    cmp(int i){
        ind = i;
    }
    bool operator<(const cmp a) const{
        return ind < a.ind;
    }
    // bool operator<(const int a) const{
    //     return arr[ind] < a;
    // }
};

void solve(int32_t n, int32_t K, long long A, int32_t S) { 

    arr.resize(n,-1);
    for(int i = 0; i < n; i++){
        arr[i] = skim(i+1);
    }

    vector<int32_t> chose(K);
    int sum = 0;
    for(int i = 0; i < K; i++){
        chose[i] = i;
        sum += arr[i];
    }

    if(sum > 2*A) {
        impossible();
    }

    priority_queue<tiii> pq;
    set<cmp> av;
    for(int i = K; i < n; i++){
        av.insert(cmp(i));
    }
    for(int i = 0; i < K; i++){
        // reevaluate
        tiii choice = {-1,i,-1}; 
            
        int bound = (2*A)-sum+arr[chose[i]];
        auto it = (av.upper_bound(bound)); 
        if(it == av.begin())continue;
        it--; 
        int j = (*it).ind;

        int del = -arr[chose[i]]+arr[j]; 
        // assert(sum  <= 2*A);
        if(del <= 0) continue;
        choice = max(choice, {del, i, j}); 
        pq.push(choice);  
    }
    while(pq.size() && sum < A){
        int delta, old, nxt;

        tie(delta,old,nxt) = pq.top(); pq.pop(); 

        if(arr[nxt]-arr[chose[old]] != delta || find(chose.begin(),chose.end(),nxt) != chose.end()){
            // reevaluate
            tiii choice = {-1,old,-1}; 
            
             
            int bound = (2*A)-sum+arr[chose[old]];
            auto it = av.upper_bound(bound); 
            if(it == av.begin())continue;
            it--; 
            int j = (*it).ind;

            int del = arr[j]-arr[chose[old]]; 
            // assert(sum <= 2*A);
            if(del <= 0) continue;
            choice = max(choice, {del, old, j}); 
            pq.push(choice);
            continue;
        }

        int oind = chose[old];
        chose[old] = nxt;
        sum += delta; 
        av.insert(oind);
        av.erase(nxt);

        // this element may be reinserted
        tiii choice = {-1,old,-1};  
             
        int bound = (2*A)-sum+arr[chose[old]];
        auto it = av.upper_bound(bound); 
        if(it == av.begin())continue;
        it--; 
        int j = (*it).ind;

        int del = arr[j]-arr[chose[old]]; 
        assert(sum  <= 2*A);
        if(del <= 0) continue; 
        choice = max(choice, {del, old, j}); 
        pq.push(choice); 
    }

    if(sum < A){
        impossible();
    }else{
        for(int i = 0; i < K; i++) chose[i]++;
        answer(chose);
    }
}

• 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