2021牛客暑期多校训练营6

Hamburger Steak

#include<iostream>
#include<cstring>
#include<queue>
#include<map>
#include<set>
#include<algorithm>
#include<cmath>
#include<vector>

#define fi first
#define se second

#define lowbit(x) (x&-x)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<int,double> pid;

const int inf=0x3f3f3f3f;
const double eps=1e-8;

const int N=100010;

int n,m;

struct node{
    ll val;
    int id;
}t[N];

vector<ll> ans[N];

bool cmp(node a,node b){
    return a.val<b.val;
}

bool check(ll x){
    ll lst=0;
    ll cnt=1;
    for(int i=1;i<=n;i++){
        if(t[i].val+lst<=x){
            lst=t[i].val+lst;
        }
        else{
            ll tmp=x-lst;
            if(lst<(t[i].val-x+lst))    return false;
            else{
                lst=t[i].val-x+lst;
                cnt++;
                if(cnt>m)    return false;
            }
        }
    }
    return cnt<=m;
}

void print(ll x){
    ll lst=0;
    ll cnt=1;
    for(int i=1;i<=n;i++){
        if(t[i].val+lst<=x){
//            printf("%lld %lld %lld %lld\n",1,cnt,lst,lst+t[i].val);
            ans[t[i].id].push_back(1);
            ans[t[i].id].push_back(cnt);
            ans[t[i].id].push_back(lst);
            ans[t[i].id].push_back(lst+t[i].val);
            lst=t[i].val+lst;
            if(lst==x){
                cnt++;
                lst=0;
            }
        }
        else{
//            printf("%lld %lld %lld %lld %lld %lld %lld\n",2,cnt+1,0,t[i].val-x+lst,cnt,lst,x);
            ans[t[i].id].push_back(2);
            ans[t[i].id].push_back(cnt+1);
            ans[t[i].id].push_back(0);
            ans[t[i].id].push_back(t[i].val-x+lst);
            ans[t[i].id].push_back(cnt);
            ans[t[i].id].push_back(lst);
            ans[t[i].id].push_back(x);
            lst=t[i].val-x+lst;
            cnt++;
        }
    }
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%lld",&t[i].val);
        t[i].id=i;
    }
    sort(t+1,t+n+1,cmp);
    ll l=0,r=1e18;
    while(l<r){
        ll mid=(l+r)/2;
        if(check(mid))    r=mid;
        else    l=mid+1;
    }
    print(l);
    for(int i=1;i<=n;i++){
        for(auto v:ans[i])    printf("%lld ",v);
        puts("");
    }
}