Dịch Vòng Tốt

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho hoán vị $p_{1}, p_{2}, \dots, p_{N}$ của $1, 2, \dots, N$ . Định nghĩa:

$f (p) = \sum_{i = 1}^{N} \frac{| p_{i} - i |}{2}$

Một hoán vị được gọi là tốt nếu có thể biến đổi nó thành hoán vị đơn vị bằng tối đa $f (p)$ phép hoán đổi hai phần tử liền kề.

Cho một hoán vị, xác định những phép dịch vòng phải nào tạo ra hoán vị tốt. Phép dịch vòng phải $s$ bước biến $[p_{1}, \dots, p_{N}]$ thành $[p_{N - s + 1}, \dots, p_{N}, p_{1}, \dots, p_{N - s}]$ .

Dữ liệu vào

Dòng 1: Số nguyên $T$ — số bộ test ( $1 \leq T \leq 10^{5}$ )
Với mỗi bộ test:
- Dòng 1: Số nguyên $N$ ( $1 \leq N \leq 2 \times 10^{5}$ )
- Dòng 2: $N$ số nguyên $p_{1}, \dots, p_{N}$

Tổng $N$ trên tất cả bộ test không vượt quá $10^{6}$ .

Dữ liệu ra

Với mỗi bộ test:

Dòng 1: Số nguyên $k$ — số phép dịch vòng tốt
Dòng 2: $k$ số nguyên $s$ ( $0 \leq s < N$ ) theo thứ tự tăng dần

Ràng buộc

$1 \leq N \leq 2 \times 10^{5}$
$\sum N \leq 10^{6}$

Ví dụ

Input	Output	Giải thích
3 5 5 4 3 2 1 4 1 2 4 3 5 1 2 3 4 5	0 2 0 1 5 0 1 2 3 4	Hoán vị đơn vị luôn tốt (0 phép dịch). Hoán vị $[5, 4, 3, 2, 1]$ không có phép dịch nào cho kết quả tốt.

Ghi chú

Test 2: $N \leq 10$
Test 3-5: $T \leq 10$ , $N \leq 2000$
Test 6-11: Không ràng buộc bổ sung

Bình luận

Không có bình luận tại thời điểm này.