5/3/26, 6:49 PM Problem - B - Codeforces
Shaheen_e_Iqbal | Logout
HOME TOP CATALOG CONTESTS GYM PROBLEMSET GROUPS RATING EDU API CALENDAR HELP
PROBLEMS SUBMIT CODE MY SUBMISSIONS STATUS HACKS ROOM STANDINGS CUSTOM INVOCATION
Codeforces Round 987 (Div. 2)
B. Penchick and Satay Sticks Finished
time limit per test: 1.5 seconds Practice
memory limit per test: 256 megabytes
Penchick and his friend Kohane are touring Indonesia, and their next stop is in Surabaya!
In the bustling food stalls of Surabaya, Kohane bought n satay sticks and arranged them in a → Virtual participation
line, with the i -th satay stick having length p i . It is given that p is a permutation∗ of length n .
Virtual contest is a way to take part in past contest,
as close as possible to participation on time. It is
Penchick wants to sort the satay sticks in increasing order of length, so that p i = i for each supported only ICPC mode for virtual contests. If
you've seen these problems, a virtual contest is not
1 ≤ i ≤ n. For fun, they created a rule: they can only swap neighboring satay sticks whose
for you - solve these problems in the archive. If you
lengths differ by exactly 1 . Formally, they can perform the following operation any number of just want to solve some problem from a contest, a
virtual contest is not for you - solve this problem in
times (including zero): the archive. Never use someone else's code, read
the tutorials or communicate with other person
during a virtual contest.
Select an index i (1 ≤ i ≤ n − 1 ) such that |p i+1 − pi | = 1 ;
Swap p i and p i+1 . Start virtual contest
Determine whether it is possible to sort the permutation p , thus the satay sticks, by performing
the above operation. → Clone Contest to Mashup
∗
A permutation of length n is an array consisting of n distinct integers from 1 to n in arbitrary order. For
example, [2, 3, 1, 5, 4] is a permutation, but [1, 2, 2] is not a permutation (2 appears twice in the array), and
[1, 3, 4] is also not a permutation (n = 3 but there is 4 in the array).
→ Submit?
Input
Language: GNU G++20 13.2 (64 bit, winlib
Each test contains multiple test cases. The first line contains the number of test cases t (
5
1 ≤ t ≤ 2 ⋅ 10 ). The description of the test cases follows. Choose
Choose File No file chosen
file:
The first line of each test case contains a single integer n (1 ≤ n ≤ 2 ⋅ 10
5
) — the number
Submit
of satay sticks.
The second line of each test case contains n integers p 1 , p 2 , … , p n (1 ≤ pi ≤ n ) — the
permutation p representing the length of the satay sticks. → Contest materials
5
It is guaranteed that the sum of n over all test cases does not exceed 2 ⋅ 10 . Announcement (en)
Output Tutorial (en)
For each test case, output "YES" if it is possible to sort permutation p by performing the
operation. Otherwise, output "NO".
You can output the answer in any case (upper or lower). For example, the strings "yEs",
"yes", "Yes", and "YES" will be recognized as positive responses.
Example
input Copy
2
4
2 1 3 4
4
4 2 3 1
output Copy
YES
NO
Note
[Link] 1/2
5/3/26, 6:49 PM Problem - B - Codeforces
In the first test case, we can sort permutation p = [2, 1, 3, 4] by performing an operation on
index 1 (|p 2 − p 1 | = |1 − 2| = 1), resulting in p = [1, 2, 3, 4].
In the second test case, it can be proven that it is impossible to sort permutation
p = [4, 2, 3, 1] by performing the operation. Here is an example of a sequence of operations
that can be performed on the permutation:
Select i = 2 ( |p 3 − p 2 | = |3 − 2| = 1 ). This results in p = [4, 3, 2, 1] .
Select i = 1 ( |p 2 − p 1 | = |3 − 4| = 1 ). This results in p = [3, 4, 2, 1] .
Select i = 3 ( |p 4 − p 3 | = |1 − 2| = 1 ). This results in p = [3, 4, 1, 2] .
Unfortunately, permutation p remains unsorted after performing the operations.
Codeforces (c) Copyright 2010-2026 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: May/03/2026 18:49:22UTC+5 (k3).
Desktop version, switch to mobile version.
Privacy Policy | Terms and Conditions
Supported by
[Link] 2/2