Submission #659761

#	Time	Username	Problem	Language	Result	Execution time	Memory
659761		Mahdi	A Difficult(y) Choice (BOI21_books)	C++17	65 / 100	1 ms	336 KiB

books

#include <bits/stdc++.h>
#include "books.h"
#pragma GCC optimize("Ofast")
using namespace std;
#define F first
#define S second
#define siz(v) (int)v.size()
typedef long long ll;
typedef pair<ll, int> pii;
const int N=1e5+5;
int n, k, s;
vector<pii>v;
vector<int>res;
ll a, num[N];

ll skm(int i){
    --s;
    if(s<0)
        return 1/0;
    if(num[i]==0)
        return num[i]=skim(i);
    return num[i];
}

int bin(ll x){
    int l=-1, r=n;
    while(r-l>1){
        int m=(r+l)/2;
        if(skm(m+1)>x)
            r=m;
        else
            l=m;
    }
    return l;
}

void sol(){
    vector<int>w;
    ll sm=0;
    sort(v.begin(), v.end());
    /*for(pii fuk : v)
        cout<<"("<<fuk.F<<", "<<fuk.S<<") ";
    cout<<'\n';*/
    for(int i=0;i<k;++i){
        sm+=v[i].F;
        w.push_back(i);
    }
    w.push_back(siz(v));
    while(sm<a){
        bool kuf=0;
        for(int i=0;i<k;++i){
            if(w[i]+1!=w[i+1]){
                sm-=v[w[i]].F;
                sm+=v[w[i]+1].F;
                ++w[i];
                kuf=1;
                break;
            }
        }
        if(!kuf)
            impossible();
    }
    w.pop_back();
    for(int i=0;i<k;++i)
        w[i]=v[w[i]].S+1;
    answer(w);
}

void solve(int N, int K, long long A, int S) {
    n=N;k=K;a=A;s=S;
    int x=bin(a/k);
    ll sm=0, ls=1e18, h;
    bool z=0;
    //cout<<"aha : "<<x<<'\n';
    if(x==-1){
        vector<int>w;
        for(int j=1;j<=k;++j){
            sm+=skm(j);
            w.push_back(j);
        }
        if(sm<=2*a)
            answer(w);
        impossible();
    }
    for(int i=x;i<n && sm<a;++i){
        h=skm(i+1);
        sm+=h;
        v.push_back({h, i});
        if(h-ls>a){
            z=1;
            break;
        }
        ls=h;
    }
    if(z){
        ll hh=h;
        int j=x+siz(v)-1;
        sm-=h;
        for(int i=max(x-k+siz(v)-1, 0);i<x;++i){
            h=skm(i+1);
            sm+=h;
            v.push_back({h, i});
        }
        if(sm<a){
            sm=hh;
            vector<int>w;
            for(int i=1;i<k;++i){
                h=skm(i);
                sm+=h;
                w.push_back(i);
            }
            w.push_back(j+1);
            if(sm<=2*a)
                answer(w);
            impossible();
        }
        for(int i=max(x-k+1, 0);i<x-k+siz(v)-1;++i){
            h=skm(i+1);
            v.push_back({h, i});
        }
    }
    for(int i=max(0, x-k+1);i<x;++i){
        h=skm(i+1);
        v.push_back({h, i});
    }
    sol();
}

Compilation message (stderr)

books.cpp: In function 'll skm(int)':
books.cpp:19:17: warning: division by zero [-Wdiv-by-zero]
   19 |         return 1/0;
      |                ~^~

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