Submission #550098

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

books

#include <bits/stdc++.h>
#include "books.h"
using namespace std;
int n,m,st,md,ed,l,r;
long long num,a,qs[100005],x;
vector<pair<long long,int> > v;
vector<int> ans;
long long query(int l,int r)
{
    if(l==0)return qs[r];
    return qs[r]-qs[l-1];
}
void solve(int N, int K, long long A, int S) {
    n=N;
    m=K;
    a=A;
    st=1;
    ed=n;
    while(ed>=st)
    {
        md=(st+ed)/2;
        num=skim(md);
        if(num>=A)
        {
            ed=md-1;
        }else
        {
            st=md+1;
        }
    }
    for(int i=1;i<=min(m,n);i++)
    {
        v.push_back({skim(i),i});
    }
    for(int i=st-m;i<=st;i++)
    {
        if(i>m&&i<=n)
        {
            v.push_back({skim(i),i});
        }
    }
    qs[0]=v[0].first;
    for(int i=1;i<v.size();i++)
    {
        qs[i]=qs[i-1]+v[i].first;
    }
    for(int i=0;i<=v.size()-m;i++)
    {
        x=query(i,i+m-1);
        if(x>=a&&x<=2*a)
        {
            for(int j=i;j<=i+m-1;j++)
            {
                ans.push_back(v[j].second);
            }
            answer(ans);
        }
    }
    for(int i=1;i<m;i++)
    {
        l=i-1;
        r=v.size()-m+i;
        if(l<r)
        {
            if(query(0,l)+query(r,v.size()-1)>=a&&query(0,l)+query(r,v.size()-1)<=2*a)
            {
                for(int j=0;j<=l;j++)ans.push_back(v[j].second);
                for(int j=r;j<v.size();j++)ans.push_back(v[j].second);
                answer(ans);
            }
        }
    }
    impossible();
}

Compilation message (stderr)

books.cpp: In function 'void solve(int, int, long long int, int)':
books.cpp:43:18: 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]
   43 |     for(int i=1;i<v.size();i++)
      |                 ~^~~~~~~~~
books.cpp:47:18: 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]
   47 |     for(int i=0;i<=v.size()-m;i++)
      |                 ~^~~~~~~~~~~~
books.cpp:68: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]
   68 |                 for(int j=r;j<v.size();j++)ans.push_back(v[j].second);
      |                             ~^~~~~~~~~

• 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