Submission #722546

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

books

#include <bits/stdc++.h>
#include "books.h"

#define X first
#define Y second
#define pb push_back

using namespace std;

typedef long long ll; 
typedef pair<int, int> pii; 

//     g++ books_sample.cpp sample_grader.cpp


void solve(int n, int k, long long a, int s) {
    vector<int> ans; 
    vector<pair<int, ll>> v1, v2;
    int lo = 1, hi = n + 1;

    while(hi - lo > 1) {
        int mi = (lo + hi) / 2;
        if(skim(mi) >= a) hi = mi;
        else lo = mi; 
    }
        
    // printf("hi %d\n", hi);

    for(int i = 1; i <= k; i++)
        v1.pb({i, skim(i)}); 
    for(int i = 0; i <= k; i++)
        if(hi - i > 0 && hi - i <= n) v2.pb({hi - i, skim(hi - i)}); 

    if(hi <= n && v2[0].Y <= 2 * a) {
        ll sum = v2[0].Y; 
        ans.pb(v2[0].X); 
        for(int i = 0; i < k - 1; i++) {
            sum += v1[i].Y; 
            ans.pb(v1[i].X); 
        }
        if(sum >= a && sum <= 2 * a) {
            answer(ans);
            return;
        } else ans.clear(); 
    }

    if(v2.size() <= k) {
        impossible();
        return; 
    }
    v2.erase(v2.begin()); 

    ll sum = 0; 
    for(int i = 0; i < k; i++) {
        sum += v2[i].Y; 
        ans.pb(v2[i].X); 
    }

    if(sum >= a && sum <= 2 * a) {
        answer(ans); 
        return ;
    }

    for(int i = 0; i < k; i++) {
        sum -= v2.back().Y; 
        sum += v1[i].Y; 
        ans.pop_back();
        ans.pb(v1[i].X);
        if(sum >= a && sum <= 2 * a) {
            answer(ans); 
            return ;
        }        
    }
    impossible();
}

Compilation message (stderr)

books.cpp: In function 'void solve(int, int, long long int, int)':
books.cpp:47:18: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   47 |     if(v2.size() <= k) {
      |        ~~~~~~~~~~^~~~

• 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