Problem ID:
lmh_ivector
Points:
2.5 (partial)
Time limit:
1.0s
Memory limit:
512M
Input:
stdin
Output:
stdout
Author:
Problem types
Allowed languages
C, C++, Java, Pascal, Perl, Python
Cho ~n~ là một số nguyên dương và ~x = (x_1, x_2,…, x_n)~ là một hoán vị của dãy số ~(1,2,…, n)~. Với ~\forall i : 1 \le i \le n~, gọi ~t_i~ là số phần tử đứng trước giá trị ~i~ mà lớn hơn ~i~ trong dãy ~x~. Khi đó dãy ~t = (t_1, t_2,…, t_n)~ được gọi là dãy nghịch thế của dãy ~x = (x_1, x_2,…, x_n)~. Ví dụ: Dãy ~x = (3,2,1,6,4,5)~ thì dãy nghịch thế của nó là ~t = (2,1,0,1,1,0)~.
- ~t_1 = 2~ vì có hai số (~3~ và ~2~) đứng trước số ~1~
- ~t_2 = 1~ vì có một số (~3~) đứng trước số ~2~
- ~t_3 = 0~ vì không có số nào đứng trước số ~3~
- ~t_4 = 1~ vì có một số (~6~) đứng trước số ~4~
- ~t_5 = 1~ vì có một số (~6~) đứng trước số ~5~
- ~t_6 = 0~ vì không có số nào lớn hơn ~6~.
Vấn đề đặt ra là:
- Cho trước một dãy hoán vị ~x~, hãy tìm dãy nghịch thế của ~x~
- Cho trước một dãy nghịch thế ~t~, hãy tìm dãy hoán vị nhận ~t~ làm dãy nghịch thế.
Dữ liệu:
Gồm ~3~ dòng:
- Dòng ~1~: Chứa số nguyên dương ~n \le 10^5~.
- Dòng ~2~: Chứa dãy hoán vị ~x~ gồm ~n~ số ~x_1, x_2,…, x_n~.
- Dòng ~3~: Chứa dãy nghịch thế ~t~: gồm ~n~ số ~t_1, t_2,…, t_n~.
Kết quả:
Gồm ~2~ dòng:
- Dòng ~1~: Ghi lần lượt từng phần tử của dãy nghịch thế của ~x~
- Dòng ~2~: Ghi lần lượt từng phần tử của dãy hoán vị của ~t~
Các số trên một dòng của Input/Output files được/phải ghi cách nhau ít nhất một dấu cách
Sample Input
6
1 2 3 4 5 6
2 1 0 1 1 0
Sample Output
0 0 0 0 0 0
3 2 1 6 4 5
Nguồn: thầy Lê Minh Hoàng
Comments