Submission #600103

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

books

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

int n,k,s;
long long a,curr,val,sum,sum2;
vector< pair<long long,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-1;i++){
        w.push_back({skim(i),i});
        sum+=w.back().first;
    }
    for(int i=max(k,r-k+1);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 and val+sum>2*a){
        impossible();
    }else if(r!=n+1 and val+sum<2*a){
        for(int i=1;i<=k-1;i++){
            ans.push_back(i);
        }
        ans.push_back(r);
        answer(ans);
    }else{
        for(int i=0;i+k-2<w.size();i++){
            curr=0; ans.clear();
            for(int f=i;f<=i+k-2;f++){
                curr+=w[f].first;
                ans.push_back(w[f].second);
            }
            ans.push_back(r);
            if(curr+val>=a and curr+val<=2*a){
                answer(ans);   
                return;
            }
        }
        impossible();
    }
}

Compilation message (stderr)

books.cpp: In function 'void solve(int, int, long long int, int)':
books.cpp:36:22: 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]
   36 |     for(int i=0;i+k-1<w.size();i++){
      |                 ~~~~~^~~~~~~~~
books.cpp:57:26: 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]
   57 |         for(int i=0;i+k-2<w.size();i++){
      |                     ~~~~~^~~~~~~~~

• 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