제출 #1272542

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1272542		nerrrmin	A Difficult(y) Choice (BOI21_books)	C++20	25 / 100	2 ms	440 KiB

books

#include <bits/stdc++.h>

#include "books.h"
#define pb push_back
using namespace std;
const int maxn = 2e5 + 10;
//
// --- 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.
//
long long n, k, s;
long long a;
long long x[maxn];
long long do_skim(int pos)
{

    if(!x[pos])x[pos] = skim(pos);
    return x[pos];
}
long long check(int from, int to)
{
    long long sum = 0;
    for (int i = from; i <= to; ++ i)
    {
        sum += do_skim(i);
        if(sum > 2*a)return sum;
    }
    return sum;
}
void solve(int N, int K, long long A, int S)
{

    n = N;
    k = K;
    a = A;

    int l = 1, r = n-k+1, mid, ans = -1;   /// nai golqmoto posledovateno k-1 sys suma < a
    while(l <= r)
    {
        mid = (l + r)/2;
        long long feedback = check(mid, mid+k-1);
        if(feedback < a)
        {
            l = mid + 1;
            ans = mid;
        }
        else if(feedback >= a)
        {
            if(feedback >= a && feedback <= 2*a)
            {
                vector < int > v;
                for (int i = mid; i <= mid+k-1; ++ i)
                    v.pb(i);
                answer(v);
                return;
            }
            r = mid - 1;
        }

    }
    if(ans == -1)
    {
        vector < int > v;
        long long sum = 0;
        for (int i = 1; i <= k; ++ i)
        {
            sum += do_skim(i);
            v.pb(i);
        }
        if(sum >= a && sum <= 2*a)answer(v);
        else impossible();
        return;
    }

    vector < int > v;
    long long sum = 0;
    for (int i = ans; i <= ans +k-1; ++ i)
        sum += do_skim(i);
    v.pb(ans+k);
    if(ans+k > n)
    {
        impossible();
        return;
    }
    sum += do_skim(ans+k);
    long long cut = 0;
    for (int i = ans; i <= ans + k -1; ++ i)
    {
        if(sum - do_skim(i) >= a && sum - do_skim(i) <= 2*a)
        {
            cut = i;
            break;
        }
    }
    if(!cut)
        impossible();
    else
    {
        for (int i = ans; i <= ans + k - 1; ++ i)
            if(i != cut)v.pb(i);
        answer(v);
    }

}

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