JOI 2023 - Tuyển chọn mùa xuân - Ngày 2

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.

Hội đồng thành phố JOI có \(N\) nghị viên, đánh số từ \(1\) đến \(N\). Hội đồng sắp biểu quyết \(M\) dự thảo điều lệ, đánh số từ \(1\) đến \(M\). Nếu \(A_{i,j}=1\), nghị viên \(i\) dự định bỏ phiếu tán thành dự thảo \(j\); nếu \(A_{i,j}=0\), người đó dự định bỏ phiếu phản đối.

Phiên họp diễn ra như sau:

1. Bốc thăm chọn ngẫu nhiên một trong \(N\) nghị viên làm chủ tịch.
2. Chủ tịch chỉ định một trong \(N-1\) nghị viên còn lại làm phó chủ tịch.
3. Biểu quyết các dự thảo. Chủ tịch và phó chủ tịch không bỏ phiếu; \(N-2\) nghị viên còn lại bỏ phiếu tán thành hoặc phản đối. Một dự thảo được thông qua nếu nhận được quá nửa số phiếu của những người bỏ phiếu, tức ít nhất \(\lfloor N/2\rfloor\) phiếu tán thành. Ký hiệu \(\lfloor x\rfloor\) là số nguyên lớn nhất không vượt quá \(x\).

Thị trưởng K muốn có càng nhiều điều lệ được thông qua càng tốt và đã thu thập dự định bỏ phiếu của mọi nghị viên. Với từng nghị viên, hãy tính số dự thảo được thông qua lớn nhất có thể nếu người đó được chọn làm chủ tịch, bằng cách lựa chọn phó chủ tịch phù hợp.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

N M
A_1,1 A_1,2 ... A_1,M
A_2,1 A_2,2 ... A_2,M
...
A_N,1 A_N,2 ... A_N,M

Dữ liệu ra

In \(N\) dòng ra đầu ra chuẩn. Dòng \(i\) chứa số dự thảo được thông qua lớn nhất có thể nếu nghị viên \(i\) được chọn làm chủ tịch.

Ràng buộc

• \(3\le N\le 300\,000\).
• \(1\le M\le 20\).
• \(0\le A_{i,j}\le 1\) với \(1\le i\le N\), \(1\le j\le M\).
• Mọi giá trị đầu vào đều là số nguyên.

Phân nhóm

• Nhóm 1 (8 điểm): \(N\le 300\).
• Nhóm 2 (8 điểm): \(N\le 3000\).
• Nhóm 3 (6 điểm): \(M\le 2\).
• Nhóm 4 (19 điểm): \(M\le 10\).
• Nhóm 5 (15 điểm): \(M\le 14\).
• Nhóm 6 (22 điểm): \(M\le 17\).
• Nhóm 7 (22 điểm): Không có ràng buộc bổ sung.

Ví dụ

3 3
1 0 0
1 1 0
1 1 1

3
3
2

4 12
1 1 1 0 1 1 0 1 0 1 1 0
1 1 0 1 1 0 1 1 1 1 1 0
0 0 1 1 1 0 0 0 0 0 1 1
1 0 0 0 1 1 1 1 1 0 0 0

5
4
6
6

16 4
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1

3
3
3
2
3
2
2
1
3
2
2
1
2
1
1
0

4 2
1 0
0 1
1 1
1 1

2
2
1
1

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.

Mizuyokan là một loại bánh ngọt Nhật Bản, được làm bằng cách đổ nhân chủ yếu từ đậu đỏ vào khuôn rồi làm đông bằng thạch agar.

JOI có một máy làm mizuyokan hình hộp chữ nhật dài theo phương ngang. Trên bánh có \(N-1\) đường cắt theo phương dọc. Chiều dài bánh và vị trí các đường cắt được xác định bởi \(N\) tham số \(d_1,d_2,\ldots,d_N\): tổng chiều dài là \(d_1+d_2+\cdots+d_N\), và khoảng cách giữa đường cắt thứ \(i-1\) và thứ \(i\) từ trái sang phải là \(d_i\). Quy ước đầu trái là đường cắt thứ \(0\), đầu phải là đường cắt thứ \(N\). Ban đầu, \(d_i=L_i\).

JOI dự định tổ chức \(Q\) buổi tiệc trà theo thứ tự. Buổi thứ \(j\) được mô tả bằng bốn số nguyên \(X_j,Y_j,A_j,B_j\) và diễn ra như sau:

1. Cập nhật tham số \(d_{X_j}\) thành \(Y_j\). Các cập nhật được giữ lại cho những buổi sau.
2. Làm một chiếc bánh mới, lấy phần nằm giữa đường cắt thứ \(A_j\) và thứ \(B_j\) để dùng trong buổi tiệc. JOI ăn phần còn lại.
3. Cắt phần bánh dành cho buổi tiệc tại một số đường cắt thành ít nhất một miếng, sao cho dãy độ dài các miếng, theo thứ tự vị trí ban đầu từ trái sang phải, là một dãy zíc zắc.

Dãy zíc zắc là dãy có các phần tử luân phiên tăng và giảm nghiêm ngặt. Chẳng hạn, \((2,9,2,7)\), \((7,1,9,4,6)\), \((5)\) và \((2,1)\) là các dãy zíc zắc; còn \((1,2,3)\), \((7,1,4,4,6)\) và \((2,2)\) thì không. Chính xác hơn, dãy \((x_1,x_2,\ldots,x_m)\) là zíc zắc nếu thỏa mãn ít nhất một trong hai điều kiện:

• Với mọi \(k=1,2,\ldots,m-1\): nếu \(k\) lẻ thì \(x_k<x_{k+1}\), nếu \(k\) chẵn thì \(x_k>x_{k+1}\).
• Với mọi \(k=1,2,\ldots,m-1\): nếu \(k\) lẻ thì \(x_k>x_{k+1}\), nếu \(k\) chẵn thì \(x_k<x_{k+1}\).

Để mời được nhiều bạn nhất, JOI muốn tối đa hóa số miếng thu được ở bước \(3\) của mỗi buổi tiệc. Cho các tham số ban đầu và kế hoạch các buổi tiệc, hãy tính số miếng lớn nhất cho từng buổi. Với các ràng buộc của bài, luôn tồn tại cách chia thỏa mãn điều kiện.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

N
L_1 L_2 ... L_N
Q
X_1 Y_1 A_1 B_1
X_2 Y_2 A_2 B_2
...
X_Q Y_Q A_Q B_Q

Dữ liệu ra

In \(Q\) dòng ra đầu ra chuẩn. Dòng \(j\) chứa số miếng lớn nhất có thể thu được bằng cách chia hợp lệ trong buổi tiệc thứ \(j\).

Ràng buộc

• \(1\le N\le 250\,000\).
• \(1\le L_i\le 10^9\) với \(1\le i\le N\).
• \(1\le Q\le 50\,000\).
• \(1\le X_j\le N\), \(1\le Y_j\le 10^9\) với \(1\le j\le Q\).
• \(0\le A_j<B_j\le N\) với \(1\le j\le Q\).
• Mọi giá trị đầu vào đều là số nguyên.

Phân nhóm

• Nhóm 1 (6 điểm): \(N\le 200\), \(Q\le 10\).
• Nhóm 2 (9 điểm): \(N\le 2000\), \(Q\le 10\).
• Nhóm 3 (13 điểm): \(Q\le 10\).
• Nhóm 4 (32 điểm): \(Y_j=L_{X_j}\) với mọi \(1\le j\le Q\), trong đó \(L\) là các giá trị ban đầu.
• Nhóm 5 (29 điểm): \(L_i\le 120\,000\) với mọi \(1\le i\le N\) và \(Y_j\le 120\,000\) với mọi \(1\le j\le Q\).
• Nhóm 6 (11 điểm): Không có ràng buộc bổ sung.

Ví dụ

6
5 6 8 7 4 9
1
6 9 0 5

3

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

1
2
3

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.