Submission #648073

#	Time	Username	Problem	Language	Result	Execution time	Memory
648073		berr	A Difficult(y) Choice (BOI21_books)	C++17	0 / 100	2 ms	668 KiB

books

#include <bits/stdc++.h>
#include "books.h"

using namespace std;

void solve(int N, int K, long long A, int S) 
{
    vector<int> vis(N+10);  
    vector<array<long long, 2>> v;
    long long sum=0;

    for(int l=0; l<K; l++)
    {
        long long  h=skim(l+1);
        sum+=h;
        v.push_back({h, l+1});
    }

    if(sum>=A&&sum<=2*A)
    {
        vector<int> ans;

        for(auto i: v) ans.push_back(i[1]);
         answer(ans);
    }
    else if(sum>2*A) impossible();
    else
    {
        for(int l=v.size()-1; l>=0; l--)
        {
            sum-=v[l][0];
            vis[v[l][1]]=0;

            int s=v[l][1];

            int h=v[l][0];

            for(int i=12; i>0; i--)
            {
                int tmp=s+(1<<i);

                if(tmp>N) continue;

                while(vis[tmp]) tmp++;

                if(tmp<=N)
                {
                    h=skim(tmp);
                    if(h<=2*A-sum) s=tmp;
                } 
            
            }
            h=skim(s);
            sum+=h;
            v[l][0]=h;
            v[l][1]=s;
            vis[v[l][1]]=1;

        }

        if(sum>=A&&sum<=2*A)
        {
            vector<int> ans;

            for(auto i: v) ans.push_back(i[1]);
             answer(ans);
        }
        else
        {
            return 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