Submission #850763

#	Time	Username	Problem	Language	Result	Execution time	Memory
850763		Litusiano	A Difficult(y) Choice (BOI21_books)	C++14	100 / 100	1 ms	1364 KiB

books

/*
SAMPLE GRADER for task BOOKS

USAGE:
place together with your solution and books.h in the same directory, then:
g++ <flags> sample_grader.cpp <solution_file>
e.g.:
g++ -std=c++17 sample_grader.cpp books.cpp

INPUT/OUTPUT:
The sample grader expects on standard input two lines. The first line should
contain the four integers N, K, A and S. The second line should contain a list
of N integers, the sequence of difficulties x_1 x_2 ... x_N which has to be
strictly increasing. Then, the grader writes to standard output a protocol of
all grader functions called by your program.
At the end, the grader prints your verdict.
*/
#include<bits/stdc++.h>
#include"books.h"

using namespace std;

typedef long long ll;

void solve(int N, int K, long long A, int S) {
  // TODO implement this function
  vector<long long> x(N+1,-1);
  long long sm = 0;
  for(int i = 1; i<=K; i++){
    x[i] = skim(i);
    sm += x[i];
  }
  if(sm > 2*A) impossible();
  if(sm >= A){
    vector<int> ans(K); iota(ans.begin(),ans.end(),1);
    answer(ans);
    return;
  }
  // get the swap
  int l = K-1; int r = N+1;
  while(r > l+1){
    int m = (l+r)/2;
    if(x[m] == -1) x[m] = skim(m);
    long long s1 = sm;
    if(x[m] >= A) r = m;
    else l = m;
  }
  long long s1 = sm;
  s1-=x[K]; s1+=x[r];
  if(A<= s1 && s1 <= 2*A){
    vector<int> ans;
    for(int i = 1; i<K; i++) ans.push_back(i);
    ans.push_back(r);
    answer(ans);
  } 
  
  // EL FINAL ES 2*A?
  int idx = r-1; // N - 1 + K - 1 
  set<int> ans;
  for(int i = 1; i<=K;i++) ans.insert(i); 
  for(int i = K; i>=1; i--){
    // fem els minims canvis
    if(x[idx] == -1) x[idx] = skim(idx);
    sm -= x[i];
    sm+=x[idx];
    ans.erase(i); ans.insert(idx);
    if(A <= sm && sm <= 2*A){
      vector<int> a;
      for(auto x : ans) a.push_back(x);
      answer(a);
    }
    idx--;
  }
  impossible();
}

Compilation message (stderr)

books.cpp: In function 'void solve(int, int, long long int, int)':
books.cpp:44:15: warning: unused variable 's1' [-Wunused-variable]
   44 |     long long s1 = sm;
      |               ^~

• 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