Submission #850724

#	Time	Username	Problem	Language	Result	Execution time	Memory
850724		Litusiano	A Difficult(y) Choice (BOI21_books)	C++14	10 / 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
  int l = 0; int r = N-K+2;
  //cerr<<"L: "<<l<<" "<<r<<endl;
  vector<long long> x(N+1,-1);
  int ans = -1;
  while(r > l+1){
    int m = (l+r)/2;
    if(!m) break;
    long long s = 0;
    //cerr<<"M: "<<l<<" "<<r<<" "<<m<<endl;
    for(int i = m; i<m+K; i++){
      //cerr<<i<<" ";
      if(x[i] == -1) x[i] = skim(i);
      s+=x[i];
    }
    //cerr<<"END i "<<s<<endl;
    if(A <= s && s <= 2*A){
      ans = m; break;
    }
    if(s > 2*A) r = m;
    else l = m;
  }
  //cerr<<"ANS: "<<ans<<endl;
  if(ans > -1){
    vector<int> ans1;
    for(int i = ans; i < ans+K; i++) ans1.push_back(i);
    answer(ans1);
  }
  else impossible();
}

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