Sau một giờ thi Codeforces, bạn nhận thấy một thí sinh khác trong phòng đã giải được một bài bằng unordered_set. Đã đến lúc hack!

Bạn biết rằng unordered_set sử dụng một bảng băm gồm \(n\) bucket, được đánh số từ \(0\) đến \(n-1\). Bạn không biết \(n\) và muốn xác định giá trị này.

Khi chèn số nguyên \(x\) vào bảng băm, nó được đưa vào bucket thứ \((x \bmod n)\). Nếu bucket đó đang có \(b\) phần tử thì phép chèn gây ra \(b\) xung đột băm.

Với một truy vấn gồm \(k\) số nguyên phân biệt \(x[0],x[1],\ldots,x[k-1]\), trình tương tác trả về tổng số xung đột phát sinh khi lần lượt chèn chúng vào một unordered_set rỗng. Chi phí của truy vấn là \(k\).

Ví dụ, nếu \(n=5\) và \(x=[2,15,7,27,8,30]\) thì có tổng cộng \(4\) xung đột:

Mỗi truy vấn sử dụng một unordered_set rỗng mới, nên các truy vấn hoàn toàn độc lập.

Hãy tìm \(n\) với tổng chi phí không quá \(1\,000\,000\).

Chi tiết cài đặt

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

int hack()

Hàm phải trả về giá trị bí mật \(n\). Trong một test, trình chấm có thể gọi hack() nhiều lần; mỗi lời gọi là một kịch bản độc lập.

Trong hack(), bạn có thể gọi:

long long collisions(std::vector<long long> x)

• x là một mảng các số nguyên phân biệt, với \(1\le x[i]\le 10^{18}\).
• Hàm trả về tổng số xung đột khi lần lượt chèn các phần tử của x vào một unordered_set rỗng.
• Có thể gọi hàm nhiều lần. Trong mỗi lời gọi hack(), tổng độ dài của x qua tất cả các truy vấn không được vượt quá \(1\,000\,000\).

Vì hack() có thể được gọi nhiều lần, hãy lưu ý dữ liệu còn lại từ lời gọi trước, đặc biệt là trạng thái trong các biến toàn cục.

Giới hạn chi phí \(1\,000\,000\) áp dụng riêng cho từng kịch bản. Nếu có \(t\) lời gọi hack(), tổng chi phí có thể đạt \(t\cdot 1\,000\,000\), nhưng mỗi lời gọi vẫn không được vượt quá \(1\,000\,000\).

Trình tương tác không thích ứng: các giá trị \(n\) được cố định trước khi quá trình tương tác bắt đầu.

Ví dụ

Giả sử có hai kịch bản. Trong lời gọi hack() đầu tiên, bạn thực hiện:

Từ đó, nếu xác định được \(n=5\), hack() phải trả về \(5\).

Trong lời gọi hack() tiếp theo, giả sử bạn thực hiện:

Giá trị \(n\) duy nhất phù hợp là \(2\), nên hack() phải trả về \(2\).

Ràng buộc

• \(1\le t\le 10\), trong đó \(t\) là số kịch bản.
• \(2\le n\le 10^9\).
• \(1\le x[i]\le 10^{18}\) trong mọi lời gọi collisions().

Phân nhóm

1. 8 điểm: \(n\le 500\,000\).
2. 17 điểm: \(n\le 1\,000\,000\).
3. 75 điểm: Không có ràng buộc bổ sung.

Trong subtask 3, bạn có thể nhận điểm thành phần. Gọi \(q\) là tổng chi phí lớn nhất của một lời gọi hack() trong tất cả các test thuộc subtask. Điểm của subtask được tính như sau:

Nếu trong bất kỳ test nào, lời gọi collisions() vi phạm các ràng buộc ở trên hoặc hack() trả về sai, lời giải nhận \(0\) điểm cho subtask đó.

Trình chấm mẫu

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

t
n_1
n_2
...
n_t

Với mỗi kịch bản, gọi \(m\) là giá trị hack() trả về và \(c\) là tổng chi phí truy vấn. Trình chấm mẫu in:

m c

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 1 - Hack!.