Đây là một bài toán tương tác.

Trên quầy của cửa hàng tráng miệng Bọ Chét có hai hàng thạch hai tầng đầy màu sắc (tầng trên là $a$, tầng dưới là $b$). Theo quy tắc “đông đặc bù nhau” của cửa hàng, tổng chiều cao của tầng trên và tầng dưới trong mỗi cặp thạch đúng bằng $n+1$. Ban đầu, nhân viên đã xếp hai hàng thạch theo chiều cao thành những hoán vị hoàn hảo của $1 \sim n$, nhưng tối qua, một nhân viên bọ chét hiếu động đã vô tình đảo tầng trên và tầng dưới tại một số vị trí!

Giờ đây, lễ hội tráng miệng thường niên sắp khai mạc, nên các nhân viên phải khôi phục cách sắp xếp ban đầu trước khi thạch bị đảo (tức là dãy chiều cao $a$ của tầng thạch trên trước khi bị đảo).

Bạn không thể trực tiếp quan sát chiều cao của thạch, nhưng có thể gửi lệnh đến máy đo tự động của cửa hàng: chỉ định một số vị trí $i$, máy đo sẽ đảo tầng trên và tầng dưới tại những vị trí đó, rồi trả về hiệu giữa chiều cao lớn nhất và nhỏ nhất (khoảng biến thiên) của tầng thạch trên hiện tại, cũng như hiệu giữa chiều cao lớn nhất và nhỏ nhất (khoảng biến thiên) của tầng thạch dưới. Lưu ý: tác động của mỗi lần đảo đều được giữ lại.

Bạn có thể khôi phục thành công dãy sắp xếp tầng thạch trên ban đầu chỉ với một số hữu hạn lần đảo và đo hay không?

Thư viện tương tác trước tiên chọn một hoán vị $p$ của $1\sim n$ và tạo hoán vị $b_i=n+1-p_i$. Sau đó, với mỗi chỉ số $i$, thư viện tương tác quyết định độc lập có hoán đổi hai số tại vị trí $i$ hay không. Gọi các mảng thu được sau khi hoán đổi là $a,b$. Khi đó luôn có $a_i+b_i=n+1$, nhưng $a,b$ không nhất thiết còn là các hoán vị.

Bạn biết $n$ nhưng không biết hai mảng này. Bạn có thể chọn một số vị trí và hoán đổi $a_i,b_i$ tại những vị trí đó; thư viện tương tác sẽ cho bạn biết khoảng biến thiên của hai mảng sau khi hoán đổi. Tác động của mỗi lần hoán đổi đều được giữ lại.

Nhiệm vụ của bạn là khôi phục mảng $a$ trước truy vấn đầu tiên. Nếu chỉ sau khi đồng thời thay mọi giá trị $x$ trong mảng trả về bằng $n+1-x$ thì mảng đó mới trùng với mảng cần khôi phục, đáp án cũng được coi là đúng.

Chi tiết cài đặt

Thí sinh không cần và cũng không được cài đặt hàm main.

Thí sinh cần đưa tệp tiêu đề range.h vào tệp mã nguồn recover.cpp và cài đặt hàm sau:

std::vector<int> recover(int c, int n);

• $c$ là số hiệu nhiệm vụ con hiện tại, có giá trị $1,2,3,4$ trong các bộ kiểm tra chính thức và $0$ trong ví dụ. $n$ là độ dài mảng. Thư viện tương tác gọi recover đúng một lần cho mỗi bộ kiểm tra.
• Giá trị trả về phải là một mảng số nguyên có độ dài $n$, biểu diễn $a$ trước truy vấn đầu tiên hoặc mảng thu được bằng cách lấy phần bù của toàn bộ mảng đó.

Thí sinh có thể gọi hàm sau:

std::pair<int, int> query(const std::vector<int>& positions);

• Các chỉ số trong positions phải đôi một khác nhau và thuộc $[0,n-1]$. Được phép truyền một mảng rỗng.
• Thư viện tương tác hoán đổi $a_i,b_i$ hiện tại đúng một lần tại mỗi chỉ số trong positions, rồi trả về khoảng biến thiên của $a$ hiện tại và khoảng biến thiên của $b$ hiện tại. Các lần hoán đổi giữa những truy vấn có tác động tích lũy, nhưng khi trả về đáp án, bạn phải khôi phục mảng ban đầu trước các lần hoán đổi đó.
• Khoảng biến thiên được định nghĩa là giá trị lớn nhất của mảng trừ giá trị nhỏ nhất. Vì luôn có $b_i=n+1-a_i$, hai khoảng biến thiên chắc chắn bằng nhau.
• Số lần gọi query không được vượt quá giới hạn $Q_{\max}$ của bộ kiểm tra tương ứng.

Thư viện tương tác không có tính thích ứng: các mảng ban đầu đã được xác định trước khi recover bắt đầu và không thay đổi theo các truy vấn của thí sinh. Thư viện tương tác dùng khi chấm chính thức có thể khác với thư viện tương tác mẫu được cung cấp; chương trình của thí sinh không được đọc dữ liệu nội bộ của thư viện tương tác hoặc trực tiếp thao tác với các luồng nhập, xuất chuẩn.

Cách kiểm tra chương trình

Đặt recover.cpp, range.h và grader.cpp trong tệp đính kèm vào cùng một thư mục, rồi biên dịch bằng C++17:

g++ grader.cpp recover.cpp -o recover -O2 -std=c++17
./recover < ex_range1.in

Dòng đầu tiên mà thư viện tương tác cục bộ đọc vào chứa $c,n,Q_{\max}$; dòng thứ hai chứa hoán vị $p_0,\ldots,p_{n-1}$; dòng thứ ba chứa $n$ số $0/1$, trong đó $1$ có nghĩa là hoán đổi tại vị trí đó trước khi bắt đầu tương tác. Chỉ có $c,n$ được cung cấp cho thí sinh qua các tham số của hàm; hoán vị, các dấu hiệu hoán đổi và giới hạn số truy vấn không được truyền trực tiếp cho chương trình của thí sinh.

Nếu đáp án đúng, thư viện tương tác cục bộ in Correct! ở dòng đầu tiên và Queries used: Q ở dòng thứ hai, trong đó $Q$ là số truy vấn được sử dụng trong lần gọi này. Nếu đáp án sai, thư viện in Wrong answer.; nếu một lời gọi giao diện không hợp lệ, nguyên nhân lỗi còn được ghi vào luồng lỗi chuẩn.

Ví dụ

Dữ liệu vào 1

0 6 67
3 1 6 4 2 5
0 1 1 0 1 0

Dữ liệu ra 1

Correct!
Queries used: 16

Ghi chú

Trong ví dụ, trước khi bắt đầu tương tác, $a=(3,6,1,4,5,5)$; mảng phần bù của toàn bộ mảng này là $(4,1,6,3,2,2)$. Trả về một trong hai mảng đều đúng. Lần gọi query({}) đầu tiên trả về $(5,5)$. Dữ liệu ra ở trên là kết quả chạy chương trình lời giải chuẩn trong tệp đính kèm; các chương trình đúng khác nhau có thể sử dụng số truy vấn khác nhau.

Giới hạn

Với mọi bộ dữ liệu kiểm tra, $1\le n\le 500$.

Điểm của mỗi nhiệm vụ con được tính theo bộ kiểm tra có hệ số điểm thấp nhất trong nhiệm vụ con đó; chi tiết được trình bày bên dưới.

Nhiệm vụ con

Nếu đáp án do recover trả về không đúng, các tham số của query không hợp lệ hoặc số truy vấn vượt quá $Q_{\max}$, điểm của bộ kiểm tra đó là $0$.

Ngược lại, đối với các nhiệm vụ con $1,2$, bộ kiểm tra đó được hưởng toàn bộ số điểm. Đối với các nhiệm vụ con $3,4$, gọi $Q$ là số truy vấn thực tế được sử dụng trong bộ kiểm tra đó; hệ số điểm $f(Q)$ được tính theo bảng sau:

Điểm của nhiệm vụ con $3$ là $40f(Q)$ và điểm của nhiệm vụ con $4$ là $40f(Q)$. Điểm cuối cùng được làm tròn đến $3$ chữ số sau dấu thập phân.

Giới hạn thời gian: $2\ \mathrm{s}$.

Giới hạn bộ nhớ: $512\ \mathrm{MiB}$.