Submission #649473

#	Time	Username	Problem	Language	Result	Execution time	Memory
649473		cadmiumsky	A Difficult(y) Choice (BOI21_books)	C++14	20 / 100	1 ms	336 KiB

books

#include <bits/stdc++.h>

#include "books.h"

using namespace std;
using ll = long long;
#define int ll 
const int nmax = 1e5 + 5;

namespace QUERY {
  ll v[nmax];
  set<int> ind;
  ll query(int x) {
    if(v[x] == 0) {
      v[x] = skim(x);
      ind.insert(x);
    }
    return v[x];
  }
}

ll n, k, a, s;

ll fmin(ll x) {
  return x * k + k * (k - 1) / 2;
}
ll fmax(ll x) {
  return x * k - k * (k - 1) / 2;
}
using namespace QUERY;
#define list shsflkhsdsdhsd
vector<ll> list;
vector<signed> sol;
void mksolve(int lp, ll sum = 0) {
  if(sum > 2 * a) return;
  if(sol.size() == k) {
    if(sum >= a) {
      answer(sol);
    }
    return;
  }
  lp++;
  for(int i = lp; i + k - sol.size() <= list.size(); i++) {
    sol.push_back(list[i]);
    sum += v[list[i]];
    mksolve(i, sum);
    sol.pop_back();
    sum -= v[list[i]];
  }
  return;
}

void solve(signed _N, signed _K, long long _A, signed _S) {
  n = _N;
  k = _K;
  a = _A;
  s = _S;
  
  ll liml = a, limr = 2 * a;
  while(k > 0 && query(n) < liml) {
    liml -= query(n);
    limr -= query(n);
    k--;
    sol.push_back(n);
    n--;
  }
  if(k == 0) impossible();
  
  ll sum = 0;
  for(int i = 1; i < k; i++)
    sol.push_back(i),
    sum += query(i);
  int lim = liml - sum;
  
  int l = k - 1;
  
  for(int i = 16; i >= 0; i--) {
    if(l + (1 << i) > n) continue;
    if(query(l + (1 << i)) < lim)
       l += (1 << i);
  }
  //cerr << a - sum << ' ' << query(l) << '\n';
  l++;
  if(l > n)
    impossible();
  //cerr << sum << ' ' <<a << ' ' << a - sum << ' ' << query(l) << ' ' << liml << ' ' << limr << '\n',
  sol.push_back(l);
  sort(sol.begin(), sol.end());
  sum += query(l);
  if(sum > limr && l == k) impossible();
  if(!(liml <= sum && sum <= limr)) {
    sum -= query(l);
    vector<int> nv;
    sol.pop_back();
    reverse(sol.begin(), sol.end());
    l--;
    nv.push_back(l);
    sum += query(l);
    while(sol.size() && liml > sum) {
      sum += query(--l);
      sum -= query(sol.back());
      sol.pop_back();
      nv.push_back(l);
    }
    if(sol.size() == 0 && liml > sum)	
      impossible();
    copy(nv.begin(), nv.end(), back_inserter(sol));
  }
  
  answer(sol);
}
#undef int

Compilation message (stderr)

books.cpp: In function 'void mksolve(ll, ll)':
books.cpp:36:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   36 |   if(sol.size() == k) {
      |      ~~~~~~~~~~~^~~~

• 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