Submission #1270060

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270060		escobrand	Gift (IZhO18_nicegift)	C++20	30 / 100	2090 ms	462088 KiB

nicegift

#include <bits/stdc++.h>

using namespace std;
#define all(v) v.begin(),v.end()
#define pb push_back
#define ll long long
#define ld long double
#define fi first
#define se second
#define mk make_pair

typedef pair<ll,int> pii;

const int maxn = 1e6 + 10;
ll a[maxn];
int i,n,t,k;
vector<pair<ll,vector<int>>>res;
priority_queue<pii> q;

bool solve(ll val)
{
  vector<int> ans;
  ans.reserve(k);
  for(int i = 1;i<=k;i++)
  {
    if(q.top().fi<val)
    {
      for(const int& l : ans)q.push(mk(a[l],l));
      return 0;
    }
    else 
    {
      ans.pb(q.top().se);
      q.pop();
    }
  }
  for(const int&l : ans)
  {
    a[l]-=val;
    q.push(mk(a[l],l));
  }
  res.pb(mk(val,ans));
  return 1;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>n>>k;
    for(i = 1;i<=n;i++)
    {
      cin>>a[i];
      q.push(mk(a[i],i));
    }
    
    for(ll tmp = LLONG_MAX;tmp;tmp>>=1)
    {
      while(solve(tmp));
    }
    
    if(q.top().fi)
    {
      cout<<-1;
      return 0;
    }
    
    cout<<res.size()<<'\n';
    
    for(pair<ll,vector<int>> & l : res)
    {
      cout<<l.fi<<' ';
      for(int p : l.se)cout<<p<<' ';
      cout<<'\n';
    }
    
    return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 0 / 19
• Subtask 5: 0 / 51