Phân Mảng Thành Ba Phần Bằng Nhau

Algorithms Arrays Buổi 14 — Two Pointers & Sliding Window prefix-sum two-pointers
Points
45
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
array1d
Submissions

Cho một mảng gồm n số nguyên. Kiểm tra xem có thể chia mảng thành ba đoạn con liên tiếp không rỗng sao cho tổng của ba đoạn bằng nhau hay không.\ \ Nếu có thể, in ra hai chỉ số i, j (1 ≤ i < j ≤ n) sao cho:\

  • Đoạn 1: a[1..i] \
  • Đoạn 2: a[i+1..j]\
  • Đoạn 3: a[j+1..n]\ ba đoạn có tổng bằng nhau. Nếu có nhiều cách, in ra cặp (i, j) với i nhỏ nhất, sau đó j nhỏ nhất.\ \ Nếu không thể, in ra -1.\ \ Input:\
  • Dòng 1: Số nguyên n (3 ≤ n ≤ 2·10^5).\
  • Dòng 2: n số nguyên a[i] (-10^9 ≤ a[i] ≤ 10^9).\ \ Output:\
  • In ra i j hoặc -1.
Ví dụ
Input Output
5
1 2 3 0 3
2 3
Draft saved