Submission #697977

#	Time	Username	Problem	Language	Result	Execution time	Memory
697977		_martynas	A Difficult(y) Choice (BOI21_books)	C++14	20 / 100	234 ms	1208 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.
//

#define F first
#define S second
#define PB push_back
#define all(a) (a).begin(), (a).end()

using ll = long long;

void solve(int N, int K, long long A, int S) {
    vector<pair<ll, int>> known;
    if(S >= N) {
        for(int i = 1; i <= N; i++) {
            known.PB({skim(i), i});
        }
        vector<pair<ll, int>> consider = known;
        sort(all(consider));
        consider.erase(unique(consider.begin(), consider.end()), consider.end());
        for(int i = K-1; i < consider.size(); i++) {
            if(consider[i].F >= A) {
                ll sum = consider[i].F;
                for(int j = 1; j < K; j++) sum += consider[j-1].F;
                if(A <= sum && sum <= 2*A) {
                    vector<int> ans;
                    for(int j = 1; j < K; j++) ans.PB(consider[j-1].S);
                    ans.PB(i+1);
                    answer(ans);
                }
                break;
            }
        }
        for(int i = 1; i+K-1 <= consider.size(); i++) {
            ll sum = 0;
            for(int j = 0; j < K; j++) sum += consider[i-1+j].F;
            if(A <= sum && sum <= 2*A) {
                vector<int> ans;
                for(int j = 0; j < K; j++) ans.PB(consider[i-1+j].S);
                answer(ans);
            }
        }
        impossible();
    }
    else {
        // S < N
        // S >= 40 for every test (or equal to N)
        // Therefore, N > 40 (if not testing locally)
        int lo = 1, hi = N;
        // find first x such that x >= A
        while(lo < hi) {
            int m = (lo+hi)/2;
            if(skim(m) < A) {
                lo = m+1;
            }
            else {
                hi = m;
            }
        }
        for(int i = 1; i <= K; i++) {
            known.PB({skim(i), i});
        }
        ll sum = skim(lo);
        ll mx = sum;
        for(int i = 1; i < K; i++) sum += known[i-1].F;
        if(A <= sum && sum <= 2*A) {
            vector<int> ans;
            for(int i = 1; i < K; i++) ans.PB(known[i-1].S);
            ans.PB(lo);
            answer(ans);
        }
        vector<pair<ll, int>> consider = known;
        for(int i = 1; i <= K; i++) {
            int where = lo-i+(mx < A);
            consider.PB({skim(where), where});
        }
        sort(all(consider));
        consider.erase(unique(consider.begin(), consider.end()), consider.end());
        for(int i = 1; i+K-1 <= consider.size(); i++) {
            sum = 0;
            for(int j = 0; j < K; j++) sum += consider[i-1+j].F;
            if(A <= sum && sum <= 2*A) {
                vector<int> ans;
                for(int j = 0; j < K; j++) ans.PB(consider[i-1+j].S);
                answer(ans);
            }
        }
        impossible();
    }
}
/*
6 3 10 6
1 2 3 4 5 6

6 3 15 6
1 2 3 4 5 6

6 3 100 6
1 2 3 4 197 200

6 3 16 6
1 2 3 4 5 6

15 3 42 20
7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
*/

Compilation message (stderr)

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

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 0 / 10
• Subtask 4: 0 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20