## B - 1D Pawn Editorial by en_translator

Note that, after each operation, each piece is on distinct square and a piece never jump over another by the operation (that is, a piece in the left of another does never go to the right of the latter by the operation).

Thus, the \(i\)-th piece from the left in the initial state is always the \(i\)-th piece from the left among the \(K\) pieces regardless of operations. Therefore, if we call the pieces Piece \(1\), Piece \(2\), \(\ldots\), and Piece \(K\), then Piece \(i\) is always the \(i\)-th piece from the left, so the operations can be rephrased as follows.

- If Piece \(L_i\) is on Square \(N\), do nothing.
- Otherwise, move Piece \(L_i\) one square right if there is no piece on the next square on the right. If there is a piece, do nothing.

Since the only piece that may be on the next square on the right is Piece \((L_i + 1)\) (which does not exist if \(L_i=K\)), we can rewrite as follows:

- If Piece \(L_i\) is on Square \(N\), do nothing.
- Otherwise, if \(L_i=K\), then move Piece \(L_i\) to the next square on the right.
- Otherwise, move Piece \(L_i\) one square right if the square with Piece \((L_i+1)\) is the next square on the right of the square with Piece \(L_i\). If it is, do nothing.

The problem can be solved by managing the index of square where Piece \(i\) is with an array \(A[i]\) and updating them according to the operations described above.

Finally, output \(A[i]\); then the problem is solved.

You may define Piece \((K+1)\) always on Square \((N+1)\) as a sentinel in order to reduce implementation for \(L_i=K\).

Sample code in C++ (without sentinel):

```
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k, q;
int a[201];
int x;
cin >> n >> k >> q;
for (int i = 1; i <= k; i++)cin >> a[i];
for (int i = 0; i < q; i++) {
cin >> x;
if (a[x] == n)continue;
else if (x == k)a[x]++;
else if (a[x] + 1 < a[x + 1])a[x]++;
}
for (int i = 1; i <= k; i++) {
cout << a[i];
if (i < k)cout << " ";
else cout << endl;
}
return 0;
}
```

c++ による実装例(番兵あり) :

```
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k, q;
int a[202];
int x;
cin >> n >> k >> q;
for (int i = 1; i <= k; i++)cin >> a[i];
a[k + 1] = n + 1;
for (int i = 0; i < q; i++) {
cin >> x;
if (a[x] + 1 < a[x + 1])a[x]++;
}
for (int i = 1; i <= k; i++) {
cout << a[i];
if (i < k)cout << " ";
else cout << endl;
}
return 0;
}
```

Sample code in Python:

```
n,k,q = map(int, input().split())
a = list(map(int,input().split()))
l= list(map(int,input().split()))
for i in range(q):
if(a[l[i]-1] == n):
continue
elif(l[i]==k):
a[l[i]-1]+=1
elif(a[l[i]-1]+1<a[l[i]]):
a[l[i]-1]+=1
print(*a)
```

posted:

last update: