Final Array Clinic - tìm và sửa 12 lỗi

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

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

Đề bài

Bài clinic tổng hợp này mô hình hóa 12 lỗi mảng thường gặp thành 12 đại lượng chẩn đoán phải tính đúng.

Cho mảng tĩnh có sức chứa $C$ và kích thước logic $n$:

$$a_0,a_1,\ldots,a_{n-1},\qquad 1\le n\le C,$$

cùng số nguyên $x$ và vị trí chèn 0-based $p$ với $0\le p\le n$.

Hãy tính 12 kết quả sau, theo đúng thứ tự:

1. $D_1=n$: số lần lặp của vòng duyệt đúng for (i = 0; i < n; ++i).
2. $D_2=n-1$: chỉ số hợp lệ cuối cùng.
3. $D_3=a_0$: phần tử đầu.
4. $D_4=a_{n-1}$: phần tử cuối.
5. $D_5=\sum_{i=0}^{n-1}a_i$: tổng với accumulator được khởi tạo đúng.
6. $D_6=\min_i a_i$.
7. $D_7=\max_i a_i$.
8. $D_8=\min\{i\mid a_i=x\}$, hoặc $-1$ nếu $x$ không xuất hiện.
9. $D_9=\max\{i\mid a_i=x\}$, hoặc $-1$ nếu $x$ không xuất hiện.
10. $D_{10}=|\{i\mid a_i=x\}|$.
11. $D_{11}=1$ nếu còn chỗ chèn ($n<C$), ngược lại $D_{11}=0$.
12. Tạo mảng $b$ bằng cách chèn $x$ tại chỉ số $p$ chỉ khi $n<C$; nếu $n=C$, giữ nguyên mảng. Gọi kích thước kết quả là $m$.

Nếu $n<C$ thì

$$b_i=\begin{cases} a_i,&0\le i<p,\\ x,&i=p,\\ a_{i-1},&p<i\le n, \end{cases} \qquad m=n+1.$$

Nếu $n=C$ thì $b=a$ và $m=n$.

Bài này kiểm tra trực tiếp các lỗi: off-by-one, truy cập a[n], nhầm first/last, accumulator chưa khởi tạo, min/max sai, first/last occurrence sai, count sai, capacity sai và shift sai chiều khi chèn.

Input

Dòng đầu chứa $C$, $n$, $p$, $x$. Dòng thứ hai chứa $n$ số nguyên $a_i$.

Output

Dòng 1 in lần lượt $D_1,D_2,\ldots,D_{11}$. Dòng 2 in $m$. Dòng 3 in $m$ phần tử của mảng kết quả $b$.

Subtask

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

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

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

Ví dụ

Input

7 5 2 4
4 1 4 9 2

Output

5 4 4 2 20 1 9 0 2 2 1
6
4 1 4 4 9 2

Giải thích

Có $n=5$ phần tử nên chỉ số cuối là $4$. Giá trị $4$ xuất hiện đầu tiên ở chỉ số $0$, cuối cùng ở chỉ số $2$, tổng cộng 2 lần. Vì $5<7$, có thể chèn thêm $4$ tại $p=2$.