5/22/24, 12:10 PM Problem - 1738D - Codeforces
|
stdfloat | Logout
HOME TOP CATALOG CONTESTS GYM PROBLEMSET GROUPS RATING EDU API CALENDAR HELP
PROBLEMS SUBMIT STATUS STANDINGS CUSTOM TEST
Codeforces Global Round 22
D. Permutation Addicts Finished
time limit per test: 2 seconds Practice
memory limit per test: 512 megabytes
input: standard input
output: standard output
Given a permutation a1 , a2 , … , an of integers from 1 to n , and a threshold k with → Virtual participation
0 ≤ k ≤ n, you compute a sequence b1 , b2 , … , bn as follows.
→ Clone Contest to Mashup
For every 1 ≤ i ≤ n in increasing order, let x = ai .
If x ≤ k , set bx to the last element aj (1 ≤ j < i) that aj > k. If no such element aj
→ Submit?
exists, set bx = n + 1 .
If x > k , set bx to the last element aj (1 ≤ j < i) that aj ≤ k. If no such element aj
Language: GNU G++20 13.2 (64 bit, winlibs)
exists, set bx = 0.
Choose
Choose File No file chosen
Unfortunately, after the sequence b1 , b2 , … , bn has been completely computed, the file:
permutation a1 , a2 , … , an and the threshold k are discarded.
Submit
Now you only have the sequence b1 , b2 , … , bn . Your task is to find any possible permutation
a1 , a2 , … , an and threshold k that produce the sequence b1 , b2 , … , bn . It is guaranteed
that there exists at least one pair of permutation a1 , a2 , … , an and threshold k that produce → Contest materials
the sequence b1 , b2 , … , bn .
Announcement (en)
A permutation of integers from 1 to n is a sequence of length n which contains all integers
Tutorial (en)
from 1 to n exactly once.
Input
5
Each test contains multiple test cases. The first line contains an integer t (1 ≤ t ≤ 10 ) —
the number of test cases. The following lines contain the description of each test case.
The first line of each test case contains an integer n (1 ≤ n ≤ 105 ), indicating the length of
the permutation a.
The second line of each test case contains n integers b1 , b2 , … , bn (0 ≤ bi ≤ n + 1),
indicating the elements of the sequence b.
It is guaranteed that there exists at least one pair of permutation a1 , a2 , … , an and
threshold k that produce the sequence b1 , b2 , … , bn .
It is guaranteed that the sum of n over all test cases does not exceed 105 .
Output
For each test case, output the threshold k (0 ≤ k ≤ n) in the first line, and then output the
permutation a1 , a2 , … , an (1 ≤ ai ≤ n ) in the second line such that the permutation
a1 , a2 , … , an and threshold k produce the sequence b1 , b2 , … , bn . If there are multiple
solutions, you can output any of them.
Example
input Copy
3
4
5 3 1 2
6
7 7 7 3 3 3
https://mirror.codeforces.com/problemset/problem/1738/D 1/2
5/22/24, 12:10 PM Problem - 1738D - Codeforces
6
4 4 4 0 0 0
output Copy
2
1 3 2 4
3
1 2 3 4 5 6
3
6 5 4 3 2 1
Note
For the first test case, permutation a = [1, 3, 2, 4] and threshold k = 2 will produce
sequence b as follows.
When i = 1 , x = ai = 1 ≤ k, there is no aj (1 ≤ j < i) that aj > k. Therefore,
b1 = n + 1 = 5 .
When i = 2 , x = ai = 3 > k, the last element aj that aj ≤ k is a1 . Therefore,
b3 = a1 = 1.
When i = 3 , x = ai = 2 ≤ k, the last element aj that aj > k is a2 . Therefore,
b2 = a2 = 3.
When i = 4 , x = ai = 4 > k, the last element aj that aj ≤ k is a3 . Therefore,
b4 = a3 = 2.
Finally, we obtain sequence b = [5, 3, 1, 2] .
For the second test case, permutation a = [1, 2, 3, 4, 5, 6] and threshold k = 3 will produce
sequence b as follows.
When i = 1, 2, 3 , ai ≤ k, there is no aj (1 ≤ j < i) that aj > k. Therefore,
b1 = b2 = b3 = n + 1 = 7.
When i = 4, 5, 6 , ai > k, the last element aj that aj ≤ k is a3 . Therefore,
b4 = b5 = b6 = a3 = 3.
Finally, we obtain sequence b = [7, 7, 7, 3, 3, 3].
For the third test case, permutation a = [6, 5, 4, 3, 2, 1] and threshold k = 3 will produce
sequence b as follows.
When i = 1, 2, 3 , ai > k, there is no aj (1 ≤ j < i) that aj ≤ k. Therefore,
b4 = b5 = b6 = 0 .
When i = 4, 5, 6 , ai ≤ k, the last element aj that aj > k is a3 . Therefore,
b1 = b2 = b3 = a3 = 4.
Finally, we obtain sequence b = [4, 4, 4, 0, 0, 0].
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: May/22/2024 12:06:41UTC+5 (l1).
Desktop version, switch to mobile version.
Privacy Policy
Supported by
https://mirror.codeforces.com/problemset/problem/1738/D 2/2
