Guest User

Untitled

a guest
Jan 23rd, 2018
77
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.32 KB | None | 0 0
  1. #include<iostream>
  2. #include<vector>
  3. #include<algorithm>
  4. using namespace std;
  5.  
  6. int main() {
  7.     long long n,k;
  8.     cin >> n >> k;
  9.     if (n==0) return 0;
  10.     vector<int> v;
  11.     for (int i = 1; i <= n; ++i) {
  12.         int a;
  13.         cin >> a;
  14.         v.push_back(a);
  15.     }
  16.     vector<int> original = v;
  17.     sort(v.begin(), v.end());
  18.     long long sum = 0;
  19.     int index;
  20.     for (index = 0; index < v.size(); ++index)
  21.         sum += v[index];
  22.     if (sum < k) {
  23.         cout << -1 << endl;
  24.         return 0;
  25.     }
  26.     if(!v.size() || sum == k){ cout << endl; return 0; }
  27.     sum = 0;
  28.     for (index = 0; index < v.size(); ++index) {
  29.         long long delta = index > 0 ? v[index] - v[index-1] : v[index];
  30.         delta *= v.size() - index;
  31.         if (delta + sum > k) break;
  32.         else sum += delta;
  33.     }
  34.     int i;
  35.     k -= sum;
  36.     int passes = index> 0?v[index-1]:0;
  37.     passes += k / (n-index);
  38.     k %= (n-index);
  39.     int last = v.size() - 1;
  40.     for (i=0; i<original.size(); ++i)
  41.     {
  42.         original[i] -= passes;
  43.         if (original[i]>0 && k > 0) {
  44.             original[i] --;
  45.             k--;
  46.             last = i;
  47.         }
  48.     }
  49.  
  50.     bool printed = false;
  51.     for (i = last+1; i < v.size(); ++i) {
  52.         if (original[i] > 0) {
  53.             if (printed) cout<< " ";
  54.             cout << (i+1);
  55.             printed = true;
  56.         }
  57.     }
  58.     for (i = 0; i <= last; ++i) {
  59.         if (original[i] > 0) {
  60.             if (printed) cout<< " ";
  61.             cout << (i+1);
  62.             printed = true;
  63.         }
  64.     }
  65.     cout << endl;
  66.     return 0;
  67. }
Add Comment
Please, Sign In to add comment