In the original problem, the heights are strictly increasing, as a result, there can be at most one equal pair, leading to a simple solution.↵
↵
However, what if the heights are non-decreasing, instead of strictly increasing? In this case, there can be more than one equal pair in the final heights. For example, $[1,1,2,2,3,3]$ will remain the same, in which there are three equal pairs. The fact that there can be more than one equal pairs makes it impossible for us to solve the problem based on the sum and length of the original heights. For example, $[4,4,5,5]$ and $[3,4,5,6]$ are all valid heights.↵
↵
How can we solve this modification?↵
↵
In the [Official Tutorial](https://mirror.codeforces.com/blog/entry/81565), it has been proved that the sequence of operations does not matter. So we can assume that when we process the $k$-th element, the first $k-1$ elements are already a valid sequence (but might not be in their final form).↵
↵
Let's consider the difference of a valid sequence. It can only have $0$ and $1$. For example, $[2,3,3,4]$ has difference $[1,0,1]$. How will the difference change when future slides happen?↵
↵
We can do some experiments. Supposing there is an infinite hill at the end, we will have: ↵
↵
$[2,3,3,4]$ ==> $[2,3,4,4]$ ==> $[2,3,4,5]$ ==> $[3,3,4,5]$↵
↵
And the difference array changes like this:↵
↵
$[,1,0,1]$ ==> $[,1,1,0]$ ==> $[,1,1,1]$ ==> $[,0,1,1]$↵
↵
We can see that the position of $0$ in the difference array keeps moving backward until it vanishes at the end. Then it will occur again at the front.↵
↵
In the following, we will call a $0$ in the difference array a "slot". In the above example, there is only one slot, what about multiple slots?↵
↵
Let's see another example.↵
↵
$[2,2,3,3,4]$ ==> $[2,2,3,4,4]$ ==> $[2,2,3,4,5]$ ==> $[2,3,3,4,5]$ ==> $[2,3,4,4,5]$ ==> $[2,3,4,5,5]$ ==> $[2,3,4,5,6]$↵
↵
Where the difference array goes like:↵
↵
$[,0,1,0,1]$ ==> $[,0,1,1,0]$ ==> $[,0,1,1,1]$ ==> $[,1,0,1,1]$ ==> $[,1,1,0,1]$ ==> $[,1,1,1,0]$ ==> $[,1,1,1,1]$↵
↵
We can find that the last slot goes to the end and vanishes. Then the first slot goes to the end and vanishes.↵
↵
How many steps does a slot need to vanish? We can see that it is related to its distance to the right border since the slot moves one element backward in every step.↵
↵
Now we can come to an intuition that we can maintain the positions of current slots. When we add a new element to the right, we first use the rightmost slot, then the one to its left, and so on. Also, to restore the final heights, we need to keep track of the current height of the first element.↵
↵
After all elements have been processed, we can first restore the difference array using remaining slots, then restore the final heights with the height of the first element, and the difference array.↵
↵
More details can be seen in the code.↵
↵
What's the complexity of this solution? Since a new element can create at most one slot, we can conclude that the total time complexity is still $O(n)$.↵
↵
<spoiler summary="Code">↵
```cpp↵
#include <cstdio>↵
#include <iostream>↵
#include <vector>↵
↵
using namespace std;↵
typedef long long ll;↵
↵
template <typename T> void read(T &x) {↵
x = 0;↵
char c = getchar();↵
T sig = 1;↵
for (; !isdigit(c); c = getchar())↵
if (c == '-')↵
sig = -1;↵
for (; isdigit(c); c = getchar())↵
x = (x << 3) + (x << 1) + c - '0';↵
x *= sig;↵
}↵
↵
class Solution {↵
public:↵
void solve() {↵
int n;↵
read(n);↵
ll start;↵
read(start);↵
vector<int> slots;↵
for (int i = 1; i < n; ++i) {↵
ll current;↵
read(current);↵
while (true) {↵
ll last = start + i - 1 - slots.size();↵
if (current == last) {↵
slots.emplace_back(i);↵
break;↵
}↵
if (current == last + 1)↵
break;↵
ll offer = current - last - 1;↵
if (!slots.empty()) {↵
int pos = slots.back();↵
slots.pop_back();↵
int capacity = i - pos;↵
if (offer >= capacity)↵
current -= capacity;↵
else {↵
current -= offer;↵
capacity -= offer;↵
slots.emplace_back(i - capacity);↵
}↵
} else {↵
ll delta = offer / (i + 1);↵
start += delta;↵
ll rest = offer % (i + 1);↵
if (rest > 0) {↵
start++;↵
slots.emplace_back(rest);↵
}↵
break;↵
}↵
}↵
}↵
vector<int> step(n, 1);↵
for (int i : slots)↵
step[i] = 0;↵
string ans;↵
for (int i = 0; i < n; ++i) {↵
ans += to_string(start) + " ";↵
if (i + 1 < n)↵
start += step[i + 1];↵
}↵
printf("%s", ans.c_str());↵
}↵
};↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
Solution solution = Solution();↵
solution.solve();↵
}↵
```↵
</spoiler>↵
↵
↵
However, what if the heights are non-decreasing, instead of strictly increasing? In this case, there can be more than one equal pair in the final heights. For example, $[1,1,2,2,3,3]$ will remain the same, in which there are three equal pairs. The fact that there can be more than one equal pairs makes it impossible for us to solve the problem based on the sum and length of the original heights. For example, $[4,4,5,5]$ and $[3,4,5,6]$ are all valid heights.↵
↵
How can we solve this modification?↵
↵
In the [Official Tutorial](https://mirror.codeforces.com/blog/entry/81565), it has been proved that the sequence of operations does not matter. So we can assume that when we process the $k$-th element, the first $k-1$ elements are already a valid sequence (but might not be in their final form).↵
↵
Let's consider the difference of a valid sequence. It can only have $0$ and $1$. For example, $[2,3,3,4]$ has difference $[1,0,1]$. How will the difference change when future slides happen?↵
↵
We can do some experiments. Supposing there is an infinite hill at the end, we will have: ↵
↵
$[2,3,3,4]$ ==> $[2,3,4,4]$ ==> $[2,3,4,5]$ ==> $[3,3,4,5]$↵
↵
And the difference array changes like this:↵
↵
$[,1,0,1]$ ==> $[,1,1,0]$ ==> $[,1,1,1]$ ==> $[,0,1,1]$↵
↵
We can see that the position of $0$ in the difference array keeps moving backward until it vanishes at the end. Then it will occur again at the front.↵
↵
In the following, we will call a $0$ in the difference array a "slot". In the above example, there is only one slot, what about multiple slots?↵
↵
Let's see another example.↵
↵
$[2,2,3,3,4]$ ==> $[2,2,3,4,4]$ ==> $[2,2,3,4,5]$ ==> $[2,3,3,4,5]$ ==> $[2,3,4,4,5]$ ==> $[2,3,4,5,5]$ ==> $[2,3,4,5,6]$↵
↵
Where the difference array goes like:↵
↵
$[,0,1,0,1]$ ==> $[,0,1,1,0]$ ==> $[,0,1,1,1]$ ==> $[,1,0,1,1]$ ==> $[,1,1,0,1]$ ==> $[,1,1,1,0]$ ==> $[,1,1,1,1]$↵
↵
We can find that the last slot goes to the end and vanishes. Then the first slot goes to the end and vanishes.↵
↵
How many steps does a slot need to vanish? We can see that it is related to its distance to the right border since the slot moves one element backward in every step.↵
↵
Now we can come to an intuition that we can maintain the positions of current slots. When we add a new element to the right, we first use the rightmost slot, then the one to its left, and so on. Also, to restore the final heights, we need to keep track of the current height of the first element.↵
↵
After all elements have been processed, we can first restore the difference array using remaining slots, then restore the final heights with the height of the first element, and the difference array.↵
↵
More details can be seen in the code.↵
↵
What's the complexity of this solution? Since a new element can create at most one slot, we can conclude that the total time complexity is still $O(n)$.↵
↵
<spoiler summary="Code">↵
```cpp↵
#include <cstdio>↵
#include <iostream>↵
#include <vector>↵
↵
using namespace std;↵
typedef long long ll;↵
↵
template <typename T> void read(T &x) {↵
x = 0;↵
char c = getchar();↵
T sig = 1;↵
for (; !isdigit(c); c = getchar())↵
if (c == '-')↵
sig = -1;↵
for (; isdigit(c); c = getchar())↵
x = (x << 3) + (x << 1) + c - '0';↵
x *= sig;↵
}↵
↵
class Solution {↵
public:↵
void solve() {↵
int n;↵
read(n);↵
ll start;↵
read(start);↵
vector<int> slots;↵
for (int i = 1; i < n; ++i) {↵
ll current;↵
read(current);↵
while (true) {↵
ll last = start + i - 1 - slots.size();↵
if (current == last) {↵
slots.emplace_back(i);↵
break;↵
}↵
if (current == last + 1)↵
break;↵
ll offer = current - last - 1;↵
if (!slots.empty()) {↵
int pos = slots.back();↵
slots.pop_back();↵
int capacity = i - pos;↵
if (offer >= capacity)↵
current -= capacity;↵
else {↵
current -= offer;↵
capacity -= offer;↵
slots.emplace_back(i - capacity);↵
}↵
} else {↵
ll delta = offer / (i + 1);↵
start += delta;↵
ll rest = offer % (i + 1);↵
if (rest > 0) {↵
start++;↵
slots.emplace_back(rest);↵
}↵
break;↵
}↵
}↵
}↵
vector<int> step(n, 1);↵
for (int i : slots)↵
step[i] = 0;↵
string ans;↵
for (int i = 0; i < n; ++i) {↵
ans += to_string(start) + " ";↵
if (i + 1 < n)↵
start += step[i + 1];↵
}↵
printf("%s", ans.c_str());↵
}↵
};↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
Solution solution = Solution();↵
solution.solve();↵
}↵
```↵
</spoiler>↵
↵
