Submission #424260

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

books

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

using namespace std;
typedef long long ll;


void solve(int N, int K, long long A, int S){


  vector <ll> srch(N+1, -1);

  ll suma = 0;

  for (int i = 1; i <= K; i++){

    srch[i] = skim(i);
    suma += srch[i];

  }

  if (suma > 2*A)
    impossible();

  vector <int> odg;

  if (suma >= A && suma <= 2*A){

     for (int i = 1; i <= K; i++)
        odg.push_back(i);

     answer(odg);
     return;

  }

  int l = 1, r = N + 1;

  while (l < r){

    ll mid = (l+r)/2;
    srch[mid] = skim(mid);

    if (srch[mid] >= A)
      r = mid;
    else
      l = mid + 1;

  }

  for (int i = min(N,l); i >= max(1, l - K); i--){

    if (srch[i] == -1)
      srch[i] = skim(i);

  }

  if (l > K && l <= N){

    ll nsuma = suma - srch[K] + srch[l];

    if (nsuma >= A && nsuma <= 2*A){

        for (int i = 1; i <= K - 1; i++)
            odg.push_back(i);
        odg.push_back(l);

        answer(odg);
        return;

    }

  }

  vector <bool> uklj(N + 1, false);

  for (int i = 1; i <= K; i++)
    uklj[i] = true;

  for (int i = 1; i <= min(K, l - K - 1); i++){

    suma -= srch[i];
    suma += srch[max(K+i, l-K+i-1)], uklj[max(K+i, l-K+i-1)] = true, uklj[i] = false;

    if (suma >= A && suma <= 2*A){

        for (int i = 1; i <= N; i++)
            if (uklj[i])
             odg.push_back(i);

        answer(odg);
        return;

    }

  }

  impossible();

}

• 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