Trong nhà máy của công ty JOI có \(N\) bàn, đánh số từ \(0\) đến \(N-1\), và \(N-1\) băng chuyền, đánh số từ \(0\) đến \(N-2\). Băng chuyền \(i\) nối bàn \(A_i\) với bàn \(B_i\) và vận chuyển theo đúng một trong hai hướng, nhưng không thể quan sát hướng vận chuyển. Nếu bỏ qua hướng, có thể đi giữa hai bàn bất kỳ qua các băng chuyền.

IOI là giám đốc nhà máy nhưng không nhớ hướng ban đầu của các băng chuyền. Để xác định chúng, IOI có thể thực hiện thao tác sau:

1. Chọn một số băng chuyền và đảo hướng của chúng.
2. Chọn một số bàn và đặt đúng một sản phẩm lên mỗi bàn được chọn.
3. Đồng thời, mỗi sản phẩm được xử lý như sau: nếu bàn của nó không có băng chuyền đi ra thì nó ở nguyên đó; nếu có, nó chọn một băng chuyền đi ra và chuyển sang bàn ở đầu kia. Sản phẩm chỉ đi qua một băng chuyền, rồi dừng lại, không tiếp tục đi dù bàn đích có băng chuyền đi ra.
4. Quan sát bàn nào có ít nhất một sản phẩm; không biết số lượng sản phẩm cụ thể trên từng bàn. Sau đó lấy hết sản phẩm ra.
5. Khôi phục hướng ban đầu của các băng chuyền đã đảo ở bước \(1\).

Hãy xác định hướng ban đầu của tất cả băng chuyền bằng không quá \(30\) thao tác.

Cài đặt

Đây là bài tương tác qua thư viện. Viết tệp conveyor.cpp, bao gồm conveyor.h, và cài đặt hàm:

void Solve(int N, std::vector<int> A, std::vector<int> B);

Hàm được gọi đúng một lần. N là số bàn; A, B có độ dài \(N-1\), mô tả hai đầu của từng băng chuyền. Chương trình có thể gọi hai hàm do trình chấm cung cấp:

std::vector<int> Query(std::vector<int> x, std::vector<int> y);
void Answer(std::vector<int> a);

Query(x,y) thực hiện một thao tác:

• x có độ dài \(N-1\); \(x_i=1\) nghĩa là đảo hướng băng chuyền \(i\), \(x_i=0\) nghĩa là không đảo.
• y có độ dài \(N\); \(y_j=1\) nghĩa là đặt một sản phẩm lên bàn \(j\), \(y_j=0\) nghĩa là không đặt.
• Giá trị trả về z có độ dài \(N\). Sau bước \(3\), \(z_j=1\) nếu bàn \(j\) có ít nhất một sản phẩm, ngược lại \(z_j=0\).
• Mọi phần tử của x, y, z đều là \(0\) hoặc \(1\). Được gọi Query nhiều nhất \(30\) lần.

Gọi Answer(a) đúng một lần để trả lời. a có độ dài \(N-1\), mỗi phần tử bằng \(0\) hoặc \(1\): \(a_i=0\) nếu hướng ban đầu là từ \(A_i\) đến \(B_i\), \(a_i=1\) nếu hướng ban đầu là từ \(B_i\) đến \(A_i\).

Các lỗi được báo như sau:

Bạn được phép định nghĩa các hàm khác và dùng biến toàn cục. Chương trình không được đọc hoặc ghi đầu vào chuẩn, đầu ra chuẩn hay bất kỳ tệp nào bằng bất kỳ phương thức nào; có thể ghi thông tin gỡ lỗi ra đầu ra lỗi chuẩn.

Trình chấm thật có thể thích nghi trên một số test: hướng các băng chuyền có thể chưa được cố định từ đầu, nhưng luôn tồn tại ít nhất một cách gán hướng phù hợp với tất cả câu trả lời của trình chấm cho đến thời điểm đó.

Trình chấm mẫu

Bộ tệp công khai gồm conveyor.h, grader.cpp, conveyor.cpp, compile.sh và ba tệp sample-01.txt, sample-02.txt, sample-03.txt. Có thể biên dịch bằng lệnh sau (hoặc chạy compile.sh):

g++ -std=gnu++17 -O2 -o grader grader.cpp conveyor.cpp

Trình chấm mẫu và chương trình của bạn chạy trong cùng một tiến trình; trình chấm thật sử dụng các tiến trình khác nhau.

Đầu vào của trình chấm mẫu có dạng:

N
A_0 A_1 ... A_(N-2)
B_0 B_1 ... B_(N-2)
C_0 C_1 ... C_(N-2)

\(C_i=0\) nghĩa là băng chuyền \(i\) ban đầu hướng từ \(A_i\) đến \(B_i\); \(C_i=1\) nghĩa là hướng ngược lại. Các giá trị \(C_i\) chỉ được trình chấm mẫu đọc, không được truyền vào Solve.

Nếu chấp nhận câu trả lời, trình chấm mẫu in số lần gọi Query, chẳng hạn Accepted: 22. Nếu có lỗi, nó in thông báo tương ứng, chẳng hạn Wrong Answer [4]. Khi có nhiều lỗi, chỉ một lỗi được báo.

Nếu có nhiều băng chuyền đi ra từ một bàn, trình chấm mẫu chọn ngẫu nhiên đều một trong số đó. Bộ sinh số giả ngẫu nhiên là std::mt19937, mặc định có seed \(0\), nên cùng một chương trình cho cùng kết quả khi chạy lại với cùng đầu vào. Có thể truyền seed nguyên làm đối số dòng lệnh đầu tiên, chẳng hạn ./grader 2023.

Dữ liệu vào

Bài nộp nhận dữ liệu qua các đối số của những hàm được mô tả ở trên, không đọc đầu vào chuẩn.

Dữ liệu ra

Bài nộp không ghi đầu ra chuẩn. Kết quả được gửi qua các hàm gọi lại được mô tả ở trên.

Ràng buộc

• Các giá trị \(N\) được quy định trong từng nhóm bên dưới.
• \(0\le A_i,B_i\le N-1\) với \(0\le i\le N-2\).
• Khi bỏ qua hướng của băng chuyền, có thể đi giữa mọi cặp bàn qua các băng chuyền.
• Mọi giá trị đều là số nguyên.
• Số lần gọi Query không vượt quá \(30\).

Phân nhóm

• Nhóm 1 (1 điểm): \(N=2\).
• Nhóm 2 (14 điểm): \(N=30\).
• Nhóm 3 (10 điểm): \(N=100\,000\) và \(A_i=i\), \(B_i=i+1\) với mọi \(0\le i\le N-2\).
• Nhóm 4 (75 điểm): \(N=100\,000\).

Ví dụ giao tiếp

Ví dụ 1

Dữ liệu vào của trình chấm mẫu:

3
0 2
2 1
1 0

Trao đổi lời gọi

Giải thích

Trong lần gọi Query thứ nhất, sản phẩm trên bàn \(2\) có thể đi đến bàn \(0\) hoặc bàn \(1\); do đó trình chấm cũng có thể trả về [0, 1, 0].

Trong lần gọi thứ hai, sản phẩm đặt trên bàn \(0\) đi qua băng chuyền \(0\) đến bàn \(2\) rồi dừng, không tiếp tục qua băng chuyền \(1\) đến bàn \(1\).

Ví dụ này không thỏa mãn ràng buộc của bất kỳ nhóm nào.

Ví dụ 2

Dữ liệu vào của trình chấm mẫu:

2
0
1
0

Giải thích

Đây là dữ liệu từ bộ trình chấm mẫu công khai, thỏa mãn ràng buộc nhóm \(1\).

Ví dụ 3

Dữ liệu vào của trình chấm mẫu:

30
17 25 16 7 18 20 7 20 3 4 2 6 8 26 6 11 29 5 28 18 17 22 7 10 2 16 23 16 15
9 21 0 11 1 2 2 14 17 7 28 19 6 16 13 12 3 7 18 25 24 23 27 13 17 20 16 8 20
1 1 0 0 1 1 1 1 0 0 1 1 1 1 1 1 0 1 0 1 1 0 0 0 0 0 1 1 1

Giải thích

Đây là dữ liệu từ bộ trình chấm mẫu công khai, thỏa mãn ràng buộc nhóm \(2\).

Nguồn

JOI 2022/2023 Spring Training, Contest 2, 20/03/2023. Đề gốc của JCIOI; bản dịch tiếng Việt theo giấy phép CC BY-SA 4.0.