Submission #850747

#	Time	Username	Problem	Language	Result	Execution time	Memory
850747		Litusiano	A Difficult(y) Choice (BOI21_books)	C++17	45 / 100	1 ms	1524 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;
  while(r > l+1){
    int m = (l+r)/2;
    if(x[m] == -1) x[m] = skim(m);
    long long s1 = sm;
    s1-=x[K]; s1+=x[m];
    if(A<= s1 && s1 <= 2*A){
      vector<int> ans;
      for(int i = 1; i<K; i++) ans.push_back(i);
      ans.push_back(m);
      answer(ans);
    } 
    if(s1 >= A) r = m;
    else l = m;
  }
  
  // EL FINAL ES 2*A?
  int idx = N;
  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();
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 15
• Subtask 3: 10 / 10
• Subtask 4: 15 / 15
• Subtask 5: 0 / 15
• Subtask 6: 20 / 20
• Subtask 7: 0 / 20