Submission #1163208

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163208		cnn008	A Difficult(y) Choice (BOI21_books)	C++20	0 / 100	1 ms	1176 KiB

books

#include <bits/stdc++.h>

#include "books.h"
#define ll long long

using namespace std;
//
// --- 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.
//

void solve(int N, int K, long long A, int S) {
    // TODO implement this function
    vector <ll> a(N+1,0);
    ll s1=0,s2=0;
    for(int i=1; i<=K; i++) a[i]=skim(i),s1+=a[i];
    for(int i=N; i>=N-K+1; i--) a[i]=skim(i),s2+=a[i];
    if(s1>2*A || s2<A){
        impossible();
        return;
    }
    if(s1>=A){
        vector <int> cur;
        for(int i=1; i<=K; i++) cur.push_back(i);
        answer(cur);
        return;
    }
    if(s2<=2*A){
        vector <int> cur;
        for(int i=N-K+1; i<=N; i++) cur.push_back(i);
        answer(cur);
        return;
    }
    ll s=s1,l=-1,r=-1;
    for(int i=K; i; i--){
        s-=a[i];
        s+=a[N-i+K];
        if(s>=A and s<=A+A){
            vector <int> cur;
            for(int j=1; j<i; j++) cur.push_back(j);
            for(int j=N-i+K; j<=N; j++) cur.push_back(j);
            answer(cur);
            return;
        }
        if(s>A+A){
            l=i-1;
            r=N-i+K;
            break;
        }
    }
    s-=a[r];
    int L=K+1,R=N-K;
    while(L<=R){
        int mid=(L+R)>>1;
        int ss=skim(mid);
        if(s+ss>=A and s+ss<=A+A){
            vector <int> cur;
            for(int i=1; i<=l; i++) cur.push_back(i);
            for(int i=r; i<=N; i++) cur.push_back(i);
            cur.push_back(mid);
            answer(cur);
        }else if(s+ss>A+A){
            R=mid-1;
        }else L=mid+1;
    }
    impossible();
}

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