Submission #155379

#TimeUsernameProblemLanguageResultExecution timeMemory
155379Charis02Zalmoxis (BOI18_zalmoxis)C++14
100 / 100
890 ms108280 KiB
#include<iostream> #include<stdio.h> #include<vector> #include<cmath> #include<queue> #include<string.h> #include<map> #include<set> #include<algorithm> #define ll int #define pi pair < ll,ll > #define mp(a,b) make_pair(a,b) #define rep(i,a,b) for(int i = a;i < b;i++) #define N 2000004 #define INF 1e9+7 using namespace std; ll n,k,ar[N],orig[N]; set < pi > s; ll epomeno[N]; vector < pi > res; void solve() { if((*s.begin()).first == 30) return; set < pi >::iterator it = s.begin(); pi cur = *it; swap(cur.first,cur.second); if(epomeno[cur.first] < n && ar[epomeno[cur.first]] == cur.second) { epomeno[cur.first] = epomeno[epomeno[cur.first]]; s.erase(s.begin()); } else res.push_back(cur); s.erase(s.begin()); s.insert(mp(cur.second+1,cur.first)); ar[cur.first]++; solve(); return; } bool cmp(const pi &a,const pi &b) { if(a.first == b.first) return a.second > b.second; return a.first < b.first; } int main() { ios_base::sync_with_stdio(false); cin >> n >> k; rep(i,0,n) { cin >> ar[i]; orig[i] = ar[i]; epomeno[i] = i+1; s.insert(mp(ar[i],i)); } solve(); ll cur = 0; ll sz = res.size(); ll start = 0; while(sz < k) { if(res[start].second == 0) { start++; continue; } res[start].second--; res.push_back(res[start]); sz++; } sort(res.begin(),res.end(),cmp); rep(i,0,n) { while(cur < k && res[cur].first <= i) { cout << res[cur].second << " "; cur++; } cout << orig[i] << " "; } cout << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...