Submission #865831

#	Time	Username	Problem	Language	Result	Execution time	Memory
865831		AbdelmagedNour	A Difficult(y) Choice (BOI21_books)	C++17	100 / 100	1 ms	864 KiB

books

#include <bits/stdc++.h>
#include "books.h"
using namespace std;
typedef long long ll;
ll a[100005];
ll ask(int i){
    if(!a[i])a[i]=skim(i);
    return a[i];
}
ll Sum(vector<int>v,int l,int r){
    ll res=0;
    for(int i=l;i<=r;i++)res+=ask(v[i]);
    return res;
}
void solve(int N, int K, long long A, int S) {
    int l=0;
    for(int i=17;i>=0;i--){
        int nxt=l+(1<<i);
        if(nxt<=N&&ask(nxt)<=A)l=nxt;
    }
    if(l<=K-2)return impossible();
    vector<int>v;
    ll sum=0;
    for(int i=1;i<=K-1;i++)v.push_back(i),sum+=ask(i);
    if(l<N){
        v.push_back(l+1);
        sum+=ask(l+1);
        if(A<=sum&&sum<=2*A)return answer(v);
    }
    if(l<K)return impossible();
    vector<int>arr;
    for(int i=1;i<=K;i++)arr.push_back(i),arr.push_back(l-K+i);
    sort(arr.begin(),arr.end());
    arr.erase(unique(arr.begin(),arr.end()),arr.end());
    for(int i=K-1;i<arr.size();i++){
        if(A<=Sum(arr,i-K+1,i)&&Sum(arr,i-K+1,i)<=2*A){
            return answer(vector<int>(arr.begin()+i-K+1,arr.begin()+i+1));
        }
    }
    impossible();
}

Compilation message (stderr)

books.cpp: In function 'void solve(int, int, long long int, int)':
books.cpp:35:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for(int i=K-1;i<arr.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