doctor.cpp

doctor.cpp

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <deque>
#include <cstdio>
#include <cassert>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>

using namespace std;

typedef long long int int64;
typedef vector<int64> VI;
#define REP(i,a,b) for (int64 i=int64(a); i<int64(b); ++i)

int64 N, K;
typedef map<int64, VI> MVI;
MVI mvi;
VI ans;

int main() {
  cin>>N>>K;

  int64 total = 0;
  REP(i, 0, N) {
    int cnt;
    cin>>cnt;
    total += cnt;
    if (mvi.count(cnt)==0) {
      mvi[cnt] = VI();
    }
    mvi[cnt].push_back(i);
  }

  if (K>total) {
    cout<<"-1\n";
    return 0;
  }

  int64 preconsume = 0;
  int64 remaining = N;

  for (MVI::iterator it=mvi.begin(); it!=mvi.end(); ++it) {
    int64 diff = it->first - preconsume;
    int64 affordable = K / remaining;

    if (affordable >= diff) {
      K -= diff*remaining;
    } else {
      bool exhaust = false;
      if (affordable==diff-1) {
        exhaust = true;
      }
      int64 split = K%remaining;
      typedef pair<int, bool> PIB;
      typedef vector<PIB> VIB;
      VIB candidates;
      for (MVI::iterator cit=it; cit!=mvi.end(); ++cit) {
        REP(i, 0, cit->second.size()) {
          candidates.push_back(PIB(cit->second[i], exhaust&&(it==cit)));
        }
      }
      sort(candidates.begin(), candidates.end());
      REP(i, split, candidates.size()) {
        PIB pib = candidates[i];
        ans.push_back(pib.first);
      }
      REP(i, 0, split) {
        PIB pib = candidates[i];
        if (!pib.second)
          ans.push_back(pib.first);
      }
      break;
    }

    remaining -= it->second.size();
    preconsume = it->first;
  }

  REP(i, 0, ans.size()) {
    static bool first=false;
    if (!first)
      first = true;
    else
      cout<<" ";
    cout<<ans[i]+1;
  }
  cout<<endl;

  return 0;
}