Elearning CodePath – CTP Online Judge

Chỉ số Cân bằng Chẵn/Lẻ

ARR002

🟢 Hard #Prefix Sum #Array #Interval

### 📌 Thông tin chung

---
### 📝 Định nghĩa Chỉ số Cân bằng

Cho dãy $A$ gồm $N$ số nguyên, được đánh số từ $0$ đến $N-1$.

Yêu cầu: Tìm một chỉ số $i$ ($0 \le i < N$) thỏa mãn điều kiện:
* **Dãy trước $A[i]$** là $A[0 \dots i-1]$.
* **Dãy sau $A[i]$** là $A[i+1 \dots N-1]$.

Điều kiện cân bằng:
1.  **Số lượng số chẵn trong dãy trước** bằng số lượng số chẵn trong dãy sau
2.  **Số lượng số lẻ trong dãy trước** bằng số lượng số lẻ trong dãy sau

---
### 📝 Yêu cầu

Tìm chỉ số $i$ nhỏ nhất thỏa mãn điều kiện cân bằng. Nếu không có chỉ số nào thỏa mãn, in ra $-1$.

---
### 📥 Định dạng Đầu vào

* Dòng đầu ghi số nguyên $N$ (độ dài dãy, $1 \le N \le 10^6$).
* Dòng tiếp theo ghi $N$ số nguyên $A_0, A_1, \dots, A_{N-1}$, các số cách nhau bởi dấu cách.

---
### 📤 Định dạng Đầu ra

Ghi chỉ số $i$ cần tìm hoặc $-1$ nếu không tồn tại chỉ số phù hợp.

---
### ✨ Ví dụ

| NUMBERS.INP | NUMBERS.OUT |
| :---: | :---: |
| `6` <br> `4 3 2 1 1 2 4` | `2` |
| `7` <br> `1 2 4 5 8 3 12` | `3` |

---
### 🏷 Ràng buộc

Giới hạn $N \le 10^6$ yêu cầu thuật toán $O(N)$.

| Subtask | Ràng buộc $N$ | Tỷ lệ điểm |
| :--- | :--- | :--- |
| $1$ | $N \le 1000$ |  $30\%$ |
| $2$ | $N \le 10^6$ |  $70\%$ |

---

✅ Đã AC: 0 / 3 submissions