Salaries
National Olympiad — Regional round (2014 season)
Submission name: salaries.cpp
Problem summary
Perform at most twelve salary-update rounds. In a round, replace each salary by the floor of its average with the first strictly greater salary to its right, or leave it unchanged if there is none. Accept the round only if it changes something and preserves all original equality and strict-order relations among salaries; otherwise stop and keep the previous salaries.
Input
N, followed by N initial salaries.
Output
The final salary of each employee, one per line.
Constraints
1 ≤ N ≤ 100000; 300 ≤ initial salary ≤ 100000.
Worked example
Official statement sample.
Input
4 300 1090 400 1000
Output
695 1090 700 1000
Solution analysis
- All comparisons within an update use the salaries from the previous round. Find the first greater salary to the right with a decreasing monotonic stack scanned from right to left: discard salaries at most the current one, then the stack top is its next strictly greater element.
- To check preservation, sort employee indices once by initial salary. In that order, adjacent equal original salaries must have equal candidate salaries, and adjacent distinct original salaries must remain strictly increasing. These adjacent checks imply all pairwise relations. Accept a changed, valid candidate and repeat, stopping after twelve accepted rounds.
- The sample first becomes 695,1090,700,1000, preserving order. The second candidate is 892,1090,850,1000. It reverses the original order of the first and third employees, so it is rejected and the first-round values are final.
Why it works
The monotonic stack removes only indices that cannot be the nearest greater element for the current or any earlier position. Its top therefore gives exactly the required partner. Sorted adjacent relation checks are equivalent to preservation of every equality and order relation by transitivity. The simulation consequently accepts and rejects precisely the prescribed rounds.
Watch out. An invalid round is rolled back completely. Process the nearest greater salary, not the largest salary to the right.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<algorithm>
#include<numeric>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
vector<int>salary(n),order(n);
for(int&x:salary){
cin>>x;
}
vector<int>original=salary;
iota(order.begin(),order.end(),0);
sort(order.begin(),order.end(),[&](int i,int j){
return original[i]<original[j];
});
for(int round=0;round<12;++round){
// Use a fresh array so every partner is taken from the previous round.
vector<int>next=salary;
vector<int>stack;
for(int i=n-1;i>=0;--i){
while(!stack.empty()&&salary[stack.back()]<=salary[i]){
stack.pop_back();
}
if(!stack.empty()){
next[i]=(salary[i]+salary[stack.back()])/2;
}
stack.push_back(i);
}
bool valid=true;
for(int i=1;i<n;++i){
int a=order[i-1],b=order[i];
if(original[a]==original[b]?next[a]!=next[b]:next[a]>=next[b]){
valid=false;
break;
}
}
if(!valid||next==salary){
break;
}
salary.swap(next);
}
for(int x:salary){
cout<<x<<'\n';
}
}