Submission #600181

#	Time	Username	Problem	Language	Result	Execution time	Memory
600181		alexander707070	A Difficult(y) Choice (BOI21_books)	C++14	100 / 100	2 ms	308 KiB

books

#include<bits/stdc++.h>
#define LL __int128
#include "books.h"
using namespace std;

int n,k,s;
LL a,curr,val,sum,last;
vector< pair<LL,int> > w;
vector<int> ans;

void solve(int N,int K,long long A,int S){
    n=N; k=K; a=A; s=S;

    int l=0,r=n+1,mid;
    while(l+1<r){
        mid=(l+r)/2;
        curr=skim(mid);
        if(curr>=a){
            r=mid;
        }else{
            l=mid;
        }
    }

    if(r<k)impossible();

    for(int i=1;i<=k;i++){
        w.push_back({skim(i),i});
        if(i<k)sum+=w.back().first;
    }
    for(int i=max(k+1,r-k);i<=r-1;i++){
        w.push_back({skim(i),i});
    }

    if(r!=n+1)val=skim(r);

    for(int i=0;i+k-1<w.size();i++){
        curr=0; ans.clear();
        for(int f=i;f<=i+k-1;f++){
            curr+=w[f].first;
            ans.push_back(w[f].second);
        }
        if(curr>=a and curr<=2*a){
            answer(ans);
            return;   
        }
    }

    if(r==n+1 or val+sum>2*a){
        impossible();
    }else{
        ans.clear();
        for(int i=1;i<=k-1;i++){
            ans.push_back(i);
        }
        ans.push_back(r);
        answer(ans);
    }
}

Compilation message (stderr)

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

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