1. Tóm tắt đề bài

Cho mảng ~A~ gồm ~N~ số nguyên. Kiểm tra xem mảng ~A~ có phải là mảng đối xứng hay không (đọc xuôi và ngược đều như nhau).

• Dữ liệu vào (Input):
  • Dòng 1: Số nguyên ~N~ (~1 \le N \le 10^5~).
  • Dòng 2: ~N~ số nguyên ~A_1, A_2, \dots, A_N~ (~-10^9 \le A_i \le 10^9~).
• Dữ liệu ra (Output):
  • In ra YES nếu mảng đối xứng.
  • Nếu không đối xứng: dòng 1 in NO, dòng 2 in chỉ số ~i~ đầu tiên (~1 \le i \le \lfloor N/2 \rfloor~) sao cho ~A_i \ne A_{N - i + 1}~.

2. Phân tích bài toán & Giới hạn

• Giới hạn kích thước: ~N \le 10^5~.
  • Với số lượng phần tử lên tới ~10^5~, thuật toán kiểm tra cần đạt độ phức tạp tuyến tính ~\mathcal{O}(N)~ để chạy dưới giới hạn thời gian (thường là ~1.0\text{s}~).
• Tính chất mảng đối xứng:
  • Một mảng được gọi là đối xứng khi với mọi chỉ số ~i~ chạy từ ~1~ đến ~\lfloor N/2 \rfloor~, phần tử đối diện tương ứng ~A_{N - i + 1}~ phải bằng ~A_i~.
  • Nếu xuất hiện bất kỳ vị trí ~i~ nào mà ~A_i \ne A_{N - i + 1}~, ta kết luận ngay mảng không đối xứng và vị trí ~i~ tìm thấy đầu tiên chính là kết quả cần in ra.

3. Thuật toán xử lý

• Kỹ thuật duyệt:

  1. Đọc số lượng phần tử ~N~ và toàn bộ mảng ~A~ (đánh số chỉ số từ ~1~ đến ~N~).
  2. Duyệt chỉ số ~i~ tăng dần từ ~1~ đến ~\lfloor N/2 \rfloor~:
     • So sánh giá trị ~A_i~ với giá trị đối xứng của nó là ~A_{N - i + 1}~.
     • Nếu phát hiện ~A_i \ne A_{N - i + 1}~:
       • In ra dòng đầu: NO.
       • In ra dòng thứ hai: chỉ số ~i~.
       • Dừng chương trình ngay lập tức (không cần duyệt tiếp).
  3. Nếu vòng lặp kết thúc mà không phát hiện sự khác nhau nào, in ra YES.

• Độ phức tạp:

  • Thời gian: ~\mathcal{O}(N)~ — Mỗi phần tử chỉ được so sánh tối đa 1 lần, thực hiện không quá ~5 \times 10^4~ phép so sánh (~< 0.05~ giây).
  • Không gian (bộ nhớ): ~\mathcal{O}(N)~ — Mảng ~10^5~ số nguyên chiếm khoảng ~400\text{ KB} - 800\text{ KB}~, hoàn toàn nằm trong giới hạn bộ nhớ quy định.