Array Mastery II - Source & Semantics Clinic

Nguồn: Phước Hưng OJ

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho mảng số nguyên

và hai số nguyên $x,y$. Bài kiểm tra tổng hợp yêu cầu thực hiện đúng tám phản xạ của Chương 32 trên cùng dữ liệu:

1. Kích thước suy ra từ danh sách $n$ phần tử là $N=n$; chỉ số hợp lệ lớn nhất là $n-1$.
2. Tạo bản sao độc lập $B$ với $b_i=a_i$.
3. Với parameter hàm dạng int a[], không thể suy portable độ dài mảng gốc bằng sizeof(a)/sizeof(a[0]); kết quả quy ước là UNKNOWN.
4. Tìm chỉ số 0-based đầu tiên và cuối cùng của $x$. Nếu $x$ không xuất hiện, cả hai chỉ số bằng $-1$.
5. Tính tần suất

6. Tạo mảng đảo $R$ theo

7. Tạo mảng $C$ bằng cách thay mọi $x$ bằng $y$. Số phép thay bằng đúng $f_x$; nếu $x=y$, $C=A$ nhưng số phép kích hoạt vẫn là $f_x$.
8. Trên $C$, chỉ được tăng phần tử từng đơn vị. Tìm số bước nhỏ nhất để biến $C$ thành dãy không giảm.

Bài này không sử dụng sorting, prefix sum, two pointers, chuỗi C hay mảng hai chiều.

Input

Dòng đầu chứa $n$. Dòng thứ hai chứa $n$ số nguyên $a_0,\ldots,a_{n-1}$. Dòng cuối chứa $x,y$.

Output

In lần lượt 9 dòng:

1. n n-1;
2. mảng $B$;
3. UNKNOWN;
4. first last;
5. $f_x$;
6. mảng đảo $R$;
7. số phép thay $f_x$;
8. mảng $C$;
9. số bước tăng nhỏ nhất để $C$ không giảm.

Subtask

Subtask 1 (20 điểm): $1\le n\le10$, $|a_i|,|x|,|y|\le100$.

Subtask 2 (30 điểm): $1\le n\le1000$, $|a_i|,|x|,|y|\le10^6$.

Subtask 3 (50 điểm): $1\le n\le10^5$, $|a_i|,|x|,|y|\le10^9$.

Ví dụ

Input

5
3 1 3 2 3
3 4

Output

5 4
3 1 3 2 3
UNKNOWN
0 4
3
3 2 3 1 3
3
4 1 4 2 4
5

Giải thích

Sau thay thế, $C=(4,1,4,2,4)$. Để không giảm cần tăng phần tử thứ hai thêm 3 và phần tử thứ tư thêm 2, tổng 5 bước.