#include <bits/stdc++.h> #define debug(x) cout<<#x<<" = "<<x<<"\n" //#define debug(x) x #define pb push_back #define ins insert #define fi first #define se second using namespace std; using ull = unsigned long long; using ll = long long; using ld = long double; template <typename H, typename T> ostream& operator<<(ostream& os, pair<H, T> m){ return os <<"("<< m.fi<<", "<<m.se<<")"; } template <typename H> ostream& operator<<(ostream& os, vector<H> V){ os<<"{"; for(int i=0; i<V.size(); i++){ if(i)os<<" "; os<<V[i]; } os<<"}"; return os; } void solve(); int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); solve(); } const int MAX_N = 50000; int a[MAX_N+5]; int b[MAX_N+5][2]; void solve(){ int t = 0; int n, m; cin>>n>>m; for(int i = 1; i <= n; i++){ cin>>a[i]; } int start= -1; bool flag = false; for(int i = n; i >= 1; i--){ //if(i % 1000 == 0) debug(i); start = -1; priority_queue<pair<int,int> > Q; int potrzeba = (n-i+2)/2; //liczba glosow potrzebnych int glosy = 1; int budzet = m; for(int j = i+1; j <= n; j++){ b[j][t^1] = 0; Q.push({-b[j][t] - a[j], j}); } while(glosy < potrzeba){ pair<int,int> p = Q.top(); // debug(glosy); // debug(potrzeba); if(budzet >= -p.fi){ budzet += p.fi; b[p.se][t^1] = -p.fi; glosy++; Q.pop(); }else break; } if(glosy < potrzeba) start = i; while(glosy < potrzeba){ i--; if(i == 0) { break; } glosy++; b[i][t^1] = -a[i]; potrzeba = (i+2-n)/1; } b[i][t^1] = budzet; // debug(i); if(i > 0) t^=1; else flag = true; //Q.clear(); } //debug(start); if(flag) for(int i = 1; i <= start; i++) b[i][t] = -1; for(int i = 1; i <= n; i++){ cout<<b[i][t]<<" "; } cout<<"\n"; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 | #include <bits/stdc++.h> #define debug(x) cout<<#x<<" = "<<x<<"\n" //#define debug(x) x #define pb push_back #define ins insert #define fi first #define se second using namespace std; using ull = unsigned long long; using ll = long long; using ld = long double; template <typename H, typename T> ostream& operator<<(ostream& os, pair<H, T> m){ return os <<"("<< m.fi<<", "<<m.se<<")"; } template <typename H> ostream& operator<<(ostream& os, vector<H> V){ os<<"{"; for(int i=0; i<V.size(); i++){ if(i)os<<" "; os<<V[i]; } os<<"}"; return os; } void solve(); int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); solve(); } const int MAX_N = 50000; int a[MAX_N+5]; int b[MAX_N+5][2]; void solve(){ int t = 0; int n, m; cin>>n>>m; for(int i = 1; i <= n; i++){ cin>>a[i]; } int start= -1; bool flag = false; for(int i = n; i >= 1; i--){ //if(i % 1000 == 0) debug(i); start = -1; priority_queue<pair<int,int> > Q; int potrzeba = (n-i+2)/2; //liczba glosow potrzebnych int glosy = 1; int budzet = m; for(int j = i+1; j <= n; j++){ b[j][t^1] = 0; Q.push({-b[j][t] - a[j], j}); } while(glosy < potrzeba){ pair<int,int> p = Q.top(); // debug(glosy); // debug(potrzeba); if(budzet >= -p.fi){ budzet += p.fi; b[p.se][t^1] = -p.fi; glosy++; Q.pop(); }else break; } if(glosy < potrzeba) start = i; while(glosy < potrzeba){ i--; if(i == 0) { break; } glosy++; b[i][t^1] = -a[i]; potrzeba = (i+2-n)/1; } b[i][t^1] = budzet; // debug(i); if(i > 0) t^=1; else flag = true; //Q.clear(); } //debug(start); if(flag) for(int i = 1; i <= start; i++) b[i][t] = -1; for(int i = 1; i <= n; i++){ cout<<b[i][t]<<" "; } cout<<"\n"; } |