Submission #943105

#	Time	Username	Problem	Language	Result	Execution time	Memory
943105		kokoxuya	A Difficult(y) Choice (BOI21_books)	C++14	0 / 100	1 ms	344 KiB

books

#include <bits/stdc++.h>
#include "books.h"
using namespace std;
//#define int long long
//#include <iostream>
//#include <algorithm>
#define coffeebeans 100000000000 //10e11

long long currsum;
bool checkers(int x, int K, vector<pair<int,long long>> &ans,  long long A) 
//return false if adding would make it too large
//return true if not and insert x into the vector
//ans : {index, value} pair
{
    long long temp1 = skim(x);
    long long cantake = (2 * A) - currsum;

    if ((currsum + (temp1 - ans[K].second)) > (2 * A) || (temp1 > (2 * A)))
    {
        return false;
    }
    else
    {
        long long hi = K, lo = 1, mid;
        while (hi > lo)
        {
            //printf("stuck in checkers\n");
            mid = (hi + lo)/2;
            if (((temp1 - ans[mid].second) <= cantake)) //won't exceed : go lower
            {
                //printf("replacing %d is ok\n",mid);
                hi = mid;
            }
            else
            {
                lo = mid + 1;
            }
        }
        currsum += (temp1 - ans[lo].second);
        //cout << "x : " << x << "\n";
        ans[lo] = {x,temp1};
        //printf("replaced %d", lo);
    }
    //printf ("this is currsum now : %d",currsum);
    sort(ans.begin() + 1, ans.end());
    return true;
}


void solve(int N, int K, long long A, int S) 
{
    vector<pair<int,long long>>ans(K + 1);
    long long temp1,temp2;

    //edge cases:
    long long catson = 0;
    if (A >= coffeebeans)
    {
        //printf("you entered the loop\n");
        vector<int>koko;
        for (int a = (N - K + 1); a <= N; a++)
        {
            koko.push_back(a);
        }
        for (int a = N; a > (N - K); a--)
        {
            temp1 = skim(a);
            if (temp1 >= A)
            {
                answer(koko);
            }
            else
            {
                catson += temp1;
            }
        }
        if (catson >= A)
        {
            answer(koko);
        }
        else
        {
            impossible();
        }
    }
    //end of edge cases

    for (int a = 1; a <= K; a++)
    {
        temp2 = skim(a);
        ans[a] = {a,temp2};
        currsum += temp2;
    }

    if (currsum > (2 * A))
    {
        impossible();
    }
    vector<int>kokonut;

    if ((currsum >= A) && (currsum <= (2 * A)))
    {
        for (int a = 1; a <= K; a++)
        {
            kokonut.push_back(ans[a].first);
        }
        answer(kokonut);
    }

    int hi = N,lo = K + 1,mid;
    //int anss;

    while (hi >= lo)
    {
        //printf("stuck in solve\n");
        mid = lo + (hi + lo)/2;
        if (checkers(mid, K, ans, A)) //keyi
        {
            //anss = mid;
            lo = mid + 1;
        }
        else
        {
            hi = mid - 1;
        }

        //printf("\n%d is between %d and %d", currsum, A, (2 * A));
        if ((currsum >= A) && (currsum <= (2 * A)))
        {
            for (int a = 1; a <= K; a++)
            {
                kokonut.push_back(ans[a].first);
            }
            answer(kokonut);
        }
    }

    //printf("is this one\n");
    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