JOI 2025 - Vòng thi mở rộng

JOI-kun, một nhà nghiên cứu thuật toán, đã phát triển một thiết bị có tên Máy sắp xếp nổi bọt.

Máy thao tác trên dãy số nguyên \(a=(a_1,a_2,\ldots,a_N)\) có độ dài \(N\). Khi khởi động, máy nhận giá trị ban đầu \(A_i\) cho mỗi phần tử \(a_i\) (\(1\le i\le N\)). Mỗi lần nhấn nút 1, máy lần lượt xét \(i=1,2,\ldots,N-1\); nếu \(a_i>a_{i+1}\) thì hoán đổi giá trị của \(a_i\) và \(a_{i+1}\).

Để chiếc máy hấp dẫn hơn, JOI-kun bổ sung nút 2. Khi nhấn nút này và nhập hai số nguyên \(l,r\) thỏa mãn \(1\le l\le r\le N\), máy xuất giá trị \(a_l+a_{l+1}+\cdots+a_r\).

Cho các giá trị ban đầu của dãy và trình tự thao tác trên máy, hãy tính các giá trị mà máy xuất ra khi nhấn nút 2.

Dữ liệu vào

Đọc từ đầu vào chuẩn theo định dạng:

N
A_1 A_2 ... A_N
Q
(Truy vấn 1)
(Truy vấn 2)
...
(Truy vấn Q)

\(Q\) là số thao tác. Truy vấn thứ \(j\) (\(1\le j\le Q\)) gồm các số nguyên cách nhau bởi dấu cách. Gọi \(T_j\) là số đầu tiên trên dòng:

• 1: dòng không chứa số nào khác; thao tác thứ \(j\) là nhấn nút 1.
• 2 L_j R_j: thao tác thứ \(j\) là nhấn nút 2 với hai số \(L_j,R_j\).

Dữ liệu ra

Với mỗi \(j\) thỏa mãn \(T_j=2\), xuất giá trị máy trả về trên một dòng riêng, theo đúng thứ tự truy vấn.

Ràng buộc

• \(2\le N\le 500\,000\).
• \(1\le A_i\le 10^9\) với \(1\le i\le N\).
• \(1\le Q\le 500\,000\).
• \(T_j\in\{1,2\}\) với \(1\le j\le Q\).
• Nếu \(T_j=2\) thì \(1\le L_j\le R_j\le N\).
• Tất cả giá trị đầu vào đều là số nguyên.

Phân nhóm

Mọi nhóm đều tuân theo các ràng buộc chung ở trên.

1. \(5\) điểm: Có nhiều nhất \(10\) chỉ số \(j\) (\(1\le j\le Q\)) thỏa mãn \(T_j=1\).
2. \(11\) điểm: \(N\le 150\,000\), \(Q\le 150\,000\); với mọi \(j\) có \(T_j=2\), \(L_j=R_j=1\).
3. \(15\) điểm: \(N\le 150\,000\), \(Q\le 150\,000\); \(1\le A_i\le 2\) với mọi \(1\le i\le N\).
4. \(23\) điểm: \(N\le 150\,000\), \(Q\le 150\,000\); với mọi \(j\) có \(T_j=2\), \(L_j=R_j\).
5. \(29\) điểm: \(N\le 150\,000\), \(Q\le 150\,000\).
6. \(17\) điểm: Không có ràng buộc bổ sung.

Ví dụ

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

13
3
12
5

5
1 1 2 1 2
5
2 2 3
1
2 2 4
1
2 2 4

3
4
4

Nguồn

JOI Open Contest 2025, bài Bubble Sort Machine, tác giả Masaki Nishimoto.

Bản dịch tiếng Việt từ đề của JCIOI (Ủy ban Olympic Tin học Quốc tế Nhật Bản), theo giấy phép CC BY-SA 4.0.

JOI-kun dự định tổ chức một sự kiện rút thăm sử dụng một số chẵn túi. Ban đầu, mỗi túi chứa một số bóng đỏ và một số bóng xanh; số bóng mỗi màu có thể bằng \(0\). Những người tham gia lần lượt đến cho tới khi có ít nhất một túi rỗng. Mỗi người rút một quả bóng từ mỗi túi. Nếu tổng số bóng đỏ và tổng số bóng xanh mà người đó rút được bằng nhau, người đó nhận một phần thưởng. Những quả bóng đã rút không được bỏ lại vào túi.

JOI-kun đã chuẩn bị \(N\) túi, đánh số từ \(0\) đến \(N-1\). Túi \(i\) (\(0\le i\le N-1\)) chứa \(X_i\) bóng đỏ và \(Y_i\) bóng xanh.

Sự kiện sẽ sử dụng một số túi trong số đó. Có \(Q\) phương án lựa chọn: phương án thứ \(j\) (\(1\le j\le Q\)) sử dụng các túi \(L_j,L_j+1,\ldots,R_j\), với \(R_j-L_j+1\) là số chẵn.

Để chuẩn bị phần thưởng, JOI-kun muốn biết tổng số phần thưởng lớn nhất mà những người tham gia có thể nhận trong từng phương án. Hãy viết chương trình nhận thông tin các túi và các phương án, rồi trả về giá trị này cho mỗi phương án. Các phương án được xét độc lập với số bóng ban đầu.

Chi tiết cài đặt

Nộp một tệp lottery.cpp, sử dụng chỉ thị #include "lottery.h" và cài đặt hai hàm:

void init(int N, int Q, std::vector<int> X, std::vector<int> Y);
int max_prize(int L, int R);

Hàm init được gọi đúng một lần khi bắt đầu. N là số túi JOI-kun chuẩn bị, Q là số phương án chọn túi. Hai mảng X, Y đều có độ dài \(N\); X[i], Y[i] lần lượt là số bóng đỏ và số bóng xanh trong túi \(i\) (\(0\le i\le N-1\)).

Hàm max_prize được gọi \(Q\) lần sau init. Ở lần gọi thứ \(j\) (\(1\le j\le Q\)), L và R lần lượt bằng \(L_j\) và \(R_j\). Hàm phải trả về tổng số phần thưởng lớn nhất mà những người tham gia có thể nhận trong phương án thứ \(j\).

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

Gói tệp hỗ trợ trong phần đính kèm chứa trình chấm mẫu grader.cpp, tệp tiêu đề, mã nguồn mẫu và các ví dụ. Đặt grader.cpp, lottery.cpp, lottery.h trong cùng thư mục, rồi biên dịch bằng:

g++ -std=gnu++20 -O2 -o grader grader.cpp lottery.cpp

Hoặc chạy ./compile.sh trong gói hỗ trợ. Khi biên dịch thành công, tệp thực thi grader được tạo ra. Trình chấm thật khác trình chấm mẫu. Trình chấm mẫu chạy trong một tiến trình, đọc đầu vào chuẩn và ghi kết quả ra đầu ra chuẩn.

Dữ liệu vào

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

N Q
X_0 X_1 ... X_{N-1}
Y_0 Y_1 ... Y_{N-1}
L_1 R_1
L_2 R_2
...
L_Q R_Q

Dữ liệu ra

Sau mỗi lần gọi max_prize, trình chấm mẫu xuất giá trị trả về trên một dòng của đầu ra chuẩn.

Ràng buộc

• \(2\le N\le 200\,000\).
• \(1\le Q\le 500\,000\).
• \(0\le X_i\le 10^9\) và \(0\le Y_i\le 10^9\) với \(0\le i\le N-1\).
• \(0\le L_j<R_j\le N-1\) với \(1\le j\le Q\).
• \(R_j-L_j+1\) là số chẵn với \(1\le j\le Q\).
• Tất cả giá trị đầu vào đều là số nguyên.

Phân nhóm

Mọi nhóm đều tuân theo các ràng buộc chung ở trên.

1. \(16\) điểm: \(Q\le 100\); \(X_i\le 100\), \(Y_i\le 100\) với mọi \(0\le i\le N-1\); \(R_j-L_j+1\le 100\) với mọi \(1\le j\le Q\).
2. \(16\) điểm: \(Q\le 100\); \(R_j-L_j+1\le 100\) với mọi \(1\le j\le Q\).
3. \(19\) điểm: \(Q\le 200\,000\); \(L_j\le L_{j+1}\) và \(R_j\le R_{j+1}\) với mọi \(1\le j\le Q-1\).
4. \(12\) điểm: \(N\le 20\,000\), \(Q\le 50\,000\).
5. \(14\) điểm: \(N\le 100\,000\), \(Q\le 200\,000\).
6. \(23\) điểm: Không có ràng buộc bổ sung.

Ví dụ giao tiếp

Ví dụ 1

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

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

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

2
0
2

Giải thích

Các lời gọi hàm tương ứng:

Lần gọi max_prize đầu tiên sử dụng các túi \(0,1,2,3\). Có thể đạt tổng cộng \(2\) phần thưởng như sau:

• Người thứ nhất lần lượt rút bóng đỏ, xanh, đỏ, xanh từ các túi \(0,1,2,3\). Số bóng đỏ và xanh bằng nhau nên người đó nhận một phần thưởng.
• Người thứ hai lần lượt rút bóng xanh, đỏ, đỏ, xanh từ các túi \(0,1,2,3\). Số bóng đỏ và xanh bằng nhau nên người đó nhận một phần thưởng.
• Lúc này túi \(1\) rỗng và sự kiện kết thúc.

Không thể nhận nhiều hơn \(2\) phần thưởng, nên lời gọi đầu tiên phải trả về \(2\).

Lần gọi thứ hai sử dụng các túi \(1,2,3,4\). Túi \(4\) rỗng ngay từ đầu, nên sự kiện kết thúc trước khi có người rút bóng. Lời gọi thứ hai phải trả về \(0\).

Lần gọi thứ ba sử dụng các túi \(2,3\). Có thể đạt tổng cộng \(2\) phần thưởng như sau:

• Người thứ nhất rút một bóng đỏ từ túi \(2\) và một bóng đỏ từ túi \(3\). Số bóng hai màu không bằng nhau nên người đó không nhận phần thưởng.
• Người thứ hai rút một bóng đỏ từ túi \(2\) và một bóng xanh từ túi \(3\), nên nhận một phần thưởng.
• Người thứ ba rút một bóng đỏ từ túi \(2\) và một bóng xanh từ túi \(3\), nên nhận một phần thưởng.
• Lúc này cả hai túi \(2,3\) đều rỗng và sự kiện kết thúc.

Không thể nhận nhiều hơn \(2\) phần thưởng, nên lời gọi thứ ba phải trả về \(2\). Ví dụ này thỏa mãn ràng buộc của các nhóm \(1,2,4,5,6\).

Ví dụ 2

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

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

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

2
3
3
1
1

Giải thích

Các lời gọi hàm tương ứng:

Ví dụ này thỏa mãn ràng buộc của tất cả các nhóm.

Nguồn

JOI Open Contest 2025, bài Lottery, tác giả Riku Kawasaki.

Bản dịch tiếng Việt từ đề của JCIOI (Ủy ban Olympic Tin học Quốc tế Nhật Bản), theo giấy phép CC BY-SA 4.0.

Aitana và Bruno đang tham quan một vườn quốc gia ở Bolivia. Vườn quốc gia có \(N\) địa điểm và \(N-1\) con đường, mỗi đường nối hai địa điểm. Có thể đi từ bất kỳ địa điểm nào đến bất kỳ địa điểm nào khác bằng cách đi qua một số con đường.

Trong lúc đi dạo, hai người bị lạc nhau. Họ phải gặp lại bằng cách đến cùng một địa điểm vào cùng một thời điểm. Tuy nhiên, ở sâu trong rừng Amazon, họ không thể liên lạc. Mỗi người chỉ có thể dựa vào bản đồ riêng thể hiện cấu trúc các con đường. Mỗi người đã ghi các nhãn \(0,1,\ldots,N-1\) lên các địa điểm trong bản đồ của mình, nhưng cách gán nhãn của Aitana và Bruno có thể khác nhau.

Từ bây giờ, ở mỗi lượt, hai người đồng thời thực hiện một trong hai hành động: đi đến một địa điểm nối trực tiếp với địa điểm hiện tại bằng một con đường, hoặc đứng yên tại địa điểm hiện tại.

Hãy cài đặt chiến lược giúp họ gặp lại. Bài làm được trọn điểm nếu họ gặp lại trong không quá \(6d\) lượt, với \(d\) là số con đường ít nhất cần đi từ vị trí ban đầu của Aitana đến vị trí ban đầu của Bruno. Nếu họ đi ngang qua nhau ở giữa một con đường thì không được tính là gặp lại. Trong một lần chạy chương trình, bạn phải giải quyết \(Q\) tình huống.

Mô tả chi tiết

Mỗi địa điểm có một mã định danh từ \(0\) đến \(N-1\). Con đường thứ \(j\) (\(0\le j\le N-2\)) nối hai địa điểm có mã \(u_j,v_j\). Địa điểm có mã \(i\) (\(0\le i\le N-1\)) mang nhãn \(p_i\) trên bản đồ Aitana và nhãn \(q_i\) trên bản đồ Bruno. Hai dãy \((p_0,p_1,\ldots,p_{N-1})\) và \((q_0,q_1,\ldots,q_{N-1})\) đều là hoán vị của \((0,1,\ldots,N-1)\).

Aitana biết các đường nối những cặp nhãn \(A_j,B_j\) (\(0\le j\le N-2\)) và biết nhãn \(S\) của vị trí hiện tại trên bản đồ của mình. Mỗi đường thực tế nối \(u_j,v_j\) tương ứng với một đường nối \(p_{u_j},p_{v_j}\); tuy nhiên, thứ tự các đường và thứ tự hai đầu của mỗi đường khi cung cấp cho Aitana có thể bị thay đổi. Nếu vị trí ban đầu của Aitana có mã \(s\) thì \(S=p_s\).

Tương tự, Bruno biết các đường nối những cặp nhãn \(C_j,D_j\) (\(0\le j\le N-2\)), theo bản đồ của mình, và nhãn \(T\) của vị trí hiện tại. Thứ tự các đường và thứ tự hai đầu đường cũng có thể bị thay đổi. Nếu vị trí ban đầu của Bruno có mã \(t\) thì \(T=q_t\).

Từ thông tin riêng của mình, mỗi người độc lập quyết định cách di chuyển trong \(10N\) lượt tiếp theo. Aitana chọn dãy nhãn \(x_0,x_1,\ldots,x_{10N}\); Bruno chọn dãy nhãn \(y_0,y_1,\ldots,y_{10N}\). Các dãy phải thỏa mãn:

• \(x_0=S\); với mỗi \(1\le k\le 10N\), hai nhãn \(x_{k-1},x_k\) trên bản đồ Aitana chỉ cùng một địa điểm hoặc hai địa điểm nối trực tiếp bằng một con đường.
• \(y_0=T\); với mỗi \(1\le k\le 10N\), hai nhãn \(y_{k-1},y_k\) trên bản đồ Bruno chỉ cùng một địa điểm hoặc hai địa điểm nối trực tiếp bằng một con đường.

Gọi \(k^*\) là số nguyên \(k\) nhỏ nhất sao cho nhãn \(x_k\) trên bản đồ Aitana và nhãn \(y_k\) trên bản đồ Bruno chỉ cùng một địa điểm thực tế. Đây là lượt hai người gặp lại. Bài làm được trọn điểm nếu \(k^*\le 6d\).

Chi tiết cài đặt

Nộp một tệp telepathy.cpp, sử dụng chỉ thị #include "telepathy.h" và cài đặt:

std::vector<int> Aitana(int N, std::vector<int> A, std::vector<int> B,
                        int S, int subtask);
std::vector<int> Bruno(int N, std::vector<int> C, std::vector<int> D,
                       int T, int subtask);

Hàm Aitana cài đặt chiến lược của Aitana, được gọi đúng một lần cho mỗi tình huống, tổng cộng \(Q\) lần:

• N là số địa điểm.
• A, B có độ dài \(N-1\); A[j], B[j] là nhãn hai đầu của một con đường trên bản đồ Aitana (\(0\le j\le N-2\)).
• S là nhãn vị trí ban đầu của Aitana.
• subtask là số nhóm của bộ kiểm thử, thuộc \(\{1,2,3\}\).
• Hàm trả về mảng \([x_0,x_1,\ldots,x_{10N}]\), mô tả cách di chuyển theo nhãn của Aitana.

Hàm Bruno cài đặt chiến lược của Bruno, được gọi đúng một lần cho mỗi tình huống, ngay sau lời gọi Aitana, tổng cộng \(Q\) lần:

• N là số địa điểm.
• C, D có độ dài \(N-1\); C[j], D[j] là nhãn hai đầu của một con đường trên bản đồ Bruno (\(0\le j\le N-2\)).
• T là nhãn vị trí ban đầu của Bruno.
• subtask là số nhóm của bộ kiểm thử, thuộc \(\{1,2,3\}\).
• Hàm trả về mảng \([y_0,y_1,\ldots,y_{10N}]\), mô tả cách di chuyển theo nhãn của Bruno.

Các trường hợp bị chấm sai:

Chương trình có thể định nghĩa các hàm phụ trợ và biến toàn cục. Khi chấm thật, chương trình chạy thành hai tiến trình riêng, một cho Aitana và một cho Bruno; hai tiến trình không thể chia sẻ biến toàn cục.

Chương trình không được sử dụng đầu vào chuẩn, đầu ra chuẩn hoặc giao tiếp với các tệp khác bằng bất kỳ cách nào. Có thể ghi thông tin gỡ lỗi ra đầu ra lỗi chuẩn.

Gói tệp hỗ trợ trong phần đính kèm chứa trình chấm mẫu và mã nguồn mẫu. Đặt grader.cpp, telepathy.cpp, telepathy.h trong cùng thư mục rồi biên dịch bằng:

g++ -std=gnu++20 -O2 -o grader grader.cpp telepathy.cpp

Hoặc chạy ./compile.sh trong gói hỗ trợ. Khi biên dịch thành công, tệp thực thi grader được tạo ra. Trình chấm thật khác trình chấm mẫu. Trình chấm mẫu chạy trong một tiến trình, đọc đầu vào chuẩn và ghi kết quả ra đầu ra chuẩn.

Dữ liệu vào

Đầu vào của trình chấm mẫu có dạng sau; các tình huống được đánh số từ \(0\) đến \(Q-1\) và subtask là số nhóm của bộ kiểm thử:

subtask
Q
(Dữ liệu tình huống 0)
(Dữ liệu tình huống 1)
...
(Dữ liệu tình huống Q-1)

Mỗi tình huống có định dạng:

N
u_0 v_0
u_1 v_1
...
u_{N-2} v_{N-2}
p_0 p_1 ... p_{N-1}
q_0 q_1 ... q_{N-1}
s t

Ý nghĩa các biến được nêu trong phần mô tả chi tiết. Đầu vào không cung cấp trực tiếp các cạnh theo bản đồ Aitana và Bruno. Trình chấm mẫu dùng số giả ngẫu nhiên để xáo trộn các đường khi truyền đối số cho Aitana và Bruno; kết quả xáo trộn không đổi giữa các lần chạy với cùng hạt giống. Để thay hạt giống, truyền một số nguyên làm đối số đầu tiên, chẳng hạn:

./grader 20250615

Dữ liệu ra

Trình chấm mẫu xuất tổng cộng \(Q\) dòng, một dòng cho mỗi tình huống:

• Nếu hợp lệ, xuất lượt gặp nhau \(k^*\) và khoảng cách ban đầu \(d\), theo đúng thứ tự này, chẳng hạn Case #0: Accepted 5 2.
• Nếu không hợp lệ, xuất loại lỗi, chẳng hạn Case #0: Wrong Answer [1].

Trong trình chấm thật, đầu vào có thể chưa được quyết định trước khi chạy chương trình. Thông tin của các tình huống sau có thể được xác định dựa trên giá trị mà Aitana và Bruno trả về ở các tình huống trước.

Ràng buộc

Cần giải quyết nhiều nhất \(201\) tình huống, tức \(1\le Q\le 201\). Mỗi tình huống thỏa mãn:

• \(2\le N\le 200\).
• \((p_0,p_1,\ldots,p_{N-1})\) là hoán vị của các số nguyên từ \(0\) đến \(N-1\).
• \((q_0,q_1,\ldots,q_{N-1})\) là hoán vị của các số nguyên từ \(0\) đến \(N-1\).
• \(0\le u_j\le N-1\) và \(0\le v_j\le N-1\) với \(0\le j\le N-2\).
• Có thể đi từ bất kỳ địa điểm nào đến bất kỳ địa điểm nào khác qua các con đường.
• \(0\le s\le N-1\), \(0\le t\le N-1\), \(s\ne t\).

Phân nhóm

Mọi nhóm đều tuân theo các ràng buộc chung ở trên.

1. \(40\) điểm: \((p_0,p_1,\ldots,p_{N-1})=(q_0,q_1,\ldots,q_{N-1})=(0,1,\ldots,N-1)\).
2. \(40\) điểm: \(u_j=j\), \(v_j=j+1\) với mọi \(0\le j\le N-2\).
3. \(20\) điểm: Không có ràng buộc bổ sung.

Nhóm \(3\) cũng chấm các bộ kiểm thử mà tham số subtask truyền cho Aitana và Bruno bằng \(1\) hoặc \(2\).

Cách tính điểm

Với mỗi tình huống, gọi \(k^*\) là lượt gặp lại và \(d\) là khoảng cách giữa hai vị trí ban đầu. Gọi \(\alpha\) là giá trị lớn nhất của \(\frac{k^*}{d}\) trên tất cả tình huống thuộc nhóm đang xét.

Nếu chương trình bị chấm sai ở bất kỳ tình huống nào trong nhóm, điểm của nhóm đó bằng \(0\). Nếu không, bạn nhận tỉ lệ phần trăm điểm của nhóm theo bảng sau. Nếu nhiều điều kiện cùng đúng, áp dụng tỉ lệ cao nhất.

Ví dụ giao tiếp

Ví dụ 1

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

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

Lời gọi và giá trị trả về

Aitana(3, [0, 1], [1, 2], 1, 2)
[1, 0, 0, 1, 2, ..., 2]
Bruno(3, [1, 0], [2, 0], 2, 2)
[2, 2, 0, 0, 1, ..., 1]

Giải thích

Một số phần tử trong các giá trị trả về ở trên được lược bỏ, nhưng mỗi mảng đều có độ dài \(31\).

Trong hình, bên trái là bản đồ Aitana, ở giữa là cấu trúc đường của vườn quốc gia theo mã định danh, bên phải là bản đồ Bruno. Ba địa điểm có mã \(0,1,2\) tạo thành một đường đi. Trên bản đồ Aitana, chúng lần lượt mang nhãn \(2,1,0\); trên bản đồ Bruno, chúng lần lượt mang nhãn \(2,0,1\). Ban đầu Aitana ở địa điểm có mã \(1\), Bruno ở địa điểm có mã \(0\).

Vị trí của Aitana lần lượt có nhãn \(1,0,0,1,2,\ldots,2\) theo bản đồ của cô; vị trí của Bruno lần lượt có nhãn \(2,2,0,0,1,\ldots,1\) theo bản đồ của anh. Hai người gặp nhau khi kết thúc lượt thứ \(3\). Khi đó, Aitana ở nhãn \(1\) trên bản đồ của cô và Bruno ở nhãn \(0\) trên bản đồ của anh; hai nhãn này chỉ cùng một địa điểm thực tế.

Nguồn

JOI Open Contest 2025, bài Telepathy, tác giả Yui Hosaka và Hirotaka Yoneda.

Bản dịch tiếng Việt và hình từ đề của JCIOI (Ủy ban Olympic Tin học Quốc tế Nhật Bản), theo giấy phép CC BY-SA 4.0.