Submission #399154

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

books

#include <vector>
#include <algorithm>
#include "books.h"

//
// --- Sample implementation for the task books ---
//
// To compile this program with the sample grader, place:
//     books.h books_sample.cpp sample_grader.cpp
// in a single folder and run:
//     g++ books_sample.cpp sample_grader.cpp
// in this folder.
//

using ll = long long;

std::vector<int> combine(std::vector<int> a, std::vector<int> b) {
  for(int i = 0; i < b.size(); i++)
    a.push_back(b[i]);
  return a;
}

std::vector<int> extract(int from, int to) {
  std::vector<int> aux;
  for(int i = from; i <= to; i++)
    aux.push_back(i);
  return aux;
}

void solve(int N, int K, long long A, int S) {
    // TODO implement this function
  int pos = 1;
  for(int jump = (1 << 20); 0 < jump; jump /= 2)
    if(pos + jump <= N && skim(pos + jump) < A)
      pos += jump;
  if(pos + 1 < K) {
    impossible();
    return ;
  }

  std::vector<std::pair<int,ll>> myvec;
  myvec.push_back({0, 0});
  for(int i = 1;i <= K; i++)
    myvec.push_back({i, skim(i)});
  for(int i = std::max(K + 1, pos - K); i <= pos; i++)
    myvec.push_back({i, skim(i)});

  if(pos < N) {
    ll sum = 0;
    for(int j = 1;j < K; j++)
      sum += myvec[j].second;
    if(sum + skim(pos + 1) <= 2 * A) {
      answer(combine(extract(1, K - 1), extract(pos + 1, pos + 1)));
      return ;
    }
  }
  
  if(myvec.size() <= K) {
    impossible();
    return ;
  }

  for(int i = 0;i <= K; i++) {
    int j = K - i;
    ll sum = 0;
    std::vector<int> sol;
    for(int id = 1; id <= i; id++) {
      sum += myvec[id].second;
      sol.push_back(myvec[id].first);
    }
    for(int id = myvec.size() - j; id <= myvec.size() - 1; id++) {
      sum += myvec[id].second;
      sol.push_back(myvec[id].first);
    }
    if(A <= sum && sum <= 2 * A) {
      answer(sol);
      return ;
    }
  }

  impossible();
}

Compilation message (stderr)

books.cpp: In function 'std::vector<int> combine(std::vector<int>, std::vector<int>)':
books.cpp:18:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |   for(int i = 0; i < b.size(); i++)
      |                  ~~^~~~~~~~~~
books.cpp: In function 'void solve(int, int, long long int, int)':
books.cpp:58:19: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   58 |   if(myvec.size() <= K) {
      |      ~~~~~~~~~~~~~^~~~
books.cpp:71:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for(int id = myvec.size() - j; id <= myvec.size() - 1; id++) {
      |                                    ~~~^~~~~~~~~~~~~~~~~~~

• 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