Submission #1270057

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270057		escobrand	Gift (IZhO18_nicegift)	C++20	7 / 100	2095 ms	11844 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<int,int> pii;

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

bool solve(ll val)
{
  vector<int> ans;
  ans.reserve(k);
  for(int i = 1;i<=n;i++)
  {
    if(a[i]>=val)
    {
      ans.pb(i);
      if(ans.size()==k)break;
    }
  }
  if(ans.size()==k)
  {
    for(const int& l : ans)a[l]-=val;
    res.pb(mk(val,ans));
    return 1;
  }
  return 0;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>n>>k;
    for(i = 1;i<=n;i++)
    {
      cin>>a[i];
    }
    
    for(ll tmp = LLONG_MAX;tmp;tmp>>=1)
    {
      while(solve(tmp));
    }
    
    for(i = 1;i<=n;i++)if(a[i])
    {
      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: 0 / 11
• Subtask 3: 0 / 12
• Subtask 4: 0 / 19
• Subtask 5: 0 / 51