Asadullo là một nhà nghiên cứu xuất sắc tại APIO (Alliance for Power and Industrial Optimization). Ông đang nghiên cứu cách tạo năng lượng bằng một loại vật liệu chưa từng được biết đến.

Có \(n\) thanh rất dài làm từ vật liệu này, được mô tả bởi mảng \(v[0],v[1],\ldots,v[n-1]\). Thanh thứ \(i\) nằm ở góc

so với chiều dương của trục \(x\), theo chiều ngược kim đồng hồ.

Hiệu suất năng lượng của các thanh là

trong đó \(\operatorname{acute}(i,j)\) là góc nhọn giữa thanh \(i\) và thanh \(j\); trong bài này, góc \(90^{\circ}\) cũng được coi là góc nhọn. Cụ thể,

Ví dụ, với \(v=[5000,12500,37500]\) thì \(a=[18,45,135]\) độ:

Ta có \(\operatorname{acute}(0,1)=7500\) (tức \(27^{\circ}\)), \(\operatorname{acute}(0,2)=17500\) (tức \(63^{\circ}\)), và \(\operatorname{acute}(1,2)=25000\) (tức \(90^{\circ}\)). Hiệu suất bằng \(50000\).

Asadullo muốn xoay các thanh để tối đa hóa hiệu suất, với các hạn chế:

• Thiết bị cho phép chọn nhiều thanh và xoay đồng thời tất cả chúng cùng một góc.
• Sau mỗi thao tác, hiệu suất năng lượng không được giảm.
• Tổng số thanh được chọn qua tất cả các thao tác không được vượt quá \(2\,000\,000\).

Hãy giúp Asadullo đạt hiệu suất năng lượng lớn nhất có thể.

Chi tiết cài đặt

Bạn cần cài đặt hàm:

void energy(int n, std::vector<int> v)

• n: số thanh.
• v: mảng độ dài \(n\) mô tả vị trí ban đầu của các thanh.
• Hàm được gọi đúng một lần.

Trong hàm này, bạn có thể gọi:

void rotate(std::vector<int> t, int x)

• t là mảng các chỉ số phân biệt: \(0\le t[i]<n\) và \(t[i]\ne t[j]\) với mọi \(i<j\). Không yêu cầu t được sắp xếp.
• Thao tác xoay đồng thời mọi thanh có chỉ số trong t theo tham số x: với mỗi \(i\) thuộc t, \(v[i]\) trở thành \((v[i]+x)\bmod 50000\).
• Có thể gọi hàm nhiều lần. Tổng độ dài của t qua tất cả các lời gọi không được vượt quá \(2\,000\,000\).

Ví dụ 1

Xét lời gọi:

energy(2, [20000, 10000])

Ban đầu \(v=[20000,10000]\) và hiệu suất bằng \(10000\). Một kịch bản hợp lệ:

1. Gọi rotate([0, 1], 8000). Khi đó \(v=[28000,18000]\) và hiệu suất không đổi.
2. Gọi rotate([0], 15000). Khi đó \(v=[43000,18000]\) và hiệu suất trở thành \(25000\).

\(25000\) là hiệu suất lớn nhất có thể cho đầu vào này.

Ví dụ 2

Xét lời gọi:

energy(3, [5000, 12500, 37500])

Đây là cấu hình trong hình phía trên. Hiệu suất ban đầu đã lớn nhất, nên không cần thao tác nào.

Ràng buộc

• \(2\le n\le 100\,000\).
• \(0\le v[i]\le 49\,999\) với mọi \(0\le i<n\).
• Các phần tử của \(v\) không nhất thiết phân biệt.

Phân nhóm

1. 5 điểm: \(n=2\).
2. 11 điểm: \(v[i]<25\,000\) với mọi \(0\le i<n\).
3. 8 điểm: \(n\le 10\).
4. 15 điểm: \(n\le 100\).
5. 15 điểm: \(n\le 300\).
6. 20 điểm: \(n\le 2000\).
7. 26 điểm: Không có ràng buộc bổ sung.

Trình chấm mẫu

Trình chấm mẫu đọc:

n
v[0] v[1] ... v[n-1]

Trình chấm mẫu in hiệu suất năng lượng cuối cùng. Ngoài ra, thông tin chi tiết về các thao tác xoay được ghi vào log.txt.

Bạn có thể tải trình chấm mẫu và tệp tiêu đề ở phần đính kèm.

Nguồn: APIO 2025, bài 3 - Rotating Lines.