Contest Duration: - (local time) (100 minutes) Back to Home
Official

## 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: