Submission #1026111

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026111		happy_node	A Difficult(y) Choice (BOI21_books)	C++17	100 / 100	2 ms	1368 KiB

books

#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) {  

        ll sum=0;
        vector<bool> used(N+1);
        vector<ll> B(N+1);

        for(int i=1;i<=K;i++) {
                used[i]=true;
                B[i]=skim(i);
                sum+=B[i];
        }

        if(sum>2*A) {
                impossible();
        }       

        if(sum>=A) {
                vector<int> ans;
                for(int i=1;i<=N;i++) {
                        if(used[i]) ans.push_back(i);
                }
                answer(ans);
        }

        // sum < A

        int cur=K;
        for(int i=N;i>=1;i--) {
                if(cur<1) break;
                if(i<=cur) break;

                B[i]=skim(i);
                used[i]=true;
                sum+=B[i];

                used[cur]=false;
                sum-=B[cur];
                cur--;

                if(sum>2*A) {
                        cur++;
                        used[i]=false;
                        sum-=B[i];

                        used[cur]=true;
                        sum+=B[cur];

                        int l=cur+1,r=i-1,res=cur;
                        while(l<=r) {
                                int m=(l+r)/2;
                                if(!B[m]) B[m]=skim(m);

                                if(sum-B[cur]+B[m]<A) {
                                        res=m,l=m+1;
                                } else {
                                        r=m-1;
                                }
                        }

                        // posisi plg kanan dmn dia masih krg dari

                        if(!B[res+1]) 
                                B[res+1]=skim(res+1);

                        if(sum-B[cur]+B[res+1]<=2*A) {
                                used[cur]=false;
                                sum-=B[cur];

                                used[res+1]=true;
                                sum+=B[res+1];
                        } else {
                                // sum < A
                                assert(sum<A);
                                for(int j=res;j>=1;j--) {
                                        if(j==cur) break;
                                        if(cur<1) break;

                                        if(!B[j]) B[j]=skim(j);

                                        used[cur]=false;
                                        sum-=B[cur];
                                        used[j]=true;
                                        sum+=B[j];
                                        cur--;

                                        if(sum>=A) {
                                                assert(sum<=2*A);
                                                break;
                                        }
                                }
                        }

                        if(sum<A || sum>2*A) impossible();

                        vector<int> ans;
                        for(int i=1;i<=N;i++) {
                                if(used[i]) ans.push_back(i);
                        }
                        answer(ans); 
                } else {
                        if(sum>=A) {
                                vector<int> ans;
                                for(int i=1;i<=N;i++) {
                                        if(used[i]) ans.push_back(i);
                                }
                                answer(ans); 
                        } else {
                                continue;
                        }
                }
        }

        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