JOI 2018 Open Contest

Sắp xếp nổi bọt là một thuật toán sắp xếp dãy số. Xét dãy \(A_0,A_1,\ldots,A_{N-1}\) có độ dài \(N\), cần sắp xếp theo thứ tự không giảm. Thuật toán đổi chỗ hai số kề nhau nếu chúng chưa đúng thứ tự, bằng cách thực hiện nhiều lượt duyệt qua dãy. Cụ thể, trong một lượt, lần lượt xét \(i=0,1,\ldots,N-2\) theo đúng thứ tự này; nếu \(A_i>A_{i+1}\) thì đổi chỗ \(A_i\) và \(A_{i+1}\).

Mọi dãy đều có thể được sắp xếp không giảm sau một số lượt như vậy. Số lượt duyệt của sắp xếp nổi bọt là số lượt cần thực hiện để dãy trở thành không giảm. Nếu dãy đã không giảm thì số lượt là \(0\); không tính thêm một lượt chỉ để kiểm tra rằng dãy đã được sắp xếp.

JOI có một dãy \(A\) độ dài \(N\) và sẽ xử lý \(Q\) truy vấn thay đổi giá trị trong dãy. Ở truy vấn thứ \(j+1\), với \(0 \le j \le Q-1\), giá trị \(A_{X_j}\) được thay bằng \(V_j\). Các thay đổi được giữ lại cho những truy vấn tiếp theo.

Hãy tìm số lượt duyệt của sắp xếp nổi bọt đối với dãy ngay sau mỗi truy vấn. Việc xét sắp xếp chỉ nhằm tính số lượt, không làm thay đổi dãy dùng cho các truy vấn tiếp theo.

Cài đặt

Với C++, nộp tệp cài đặt hàm sau và khai báo #include "bubblesort2.h":

std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V);

• A là mảng số nguyên độ dài \(N\), chứa dãy ban đầu.
• X và V là hai mảng số nguyên độ dài \(Q\), mô tả các truy vấn.
• Hàm trả về mảng số nguyên S độ dài \(Q\). Với mỗi \(0 \le j \le Q-1\), S[j] là số lượt duyệt của sắp xếp nổi bọt đối với dãy ngay sau truy vấn thứ \(j+1\).

Trên LQDOJ, nộp đúng một tệp C++ cài đặt hàm theo chữ ký trên. Có thể cài đặt thêm các hàm phụ. Chương trình không được đọc đầu vào chuẩn, ghi đầu ra chuẩn hoặc tương tác với bất kỳ tệp nào khác; được phép ghi ra luồng lỗi chuẩn. Gói đính kèm chính thức vẫn được giữ để tham khảo, nhưng trình chấm của bài này chỉ hỗ trợ C++. Thông báo kỳ thi gốc quy định tối đa \(50\) lần nộp cho mỗi bài.

Dữ liệu vào

Trình chấm mẫu đọc dữ liệu theo định dạng sau; chương trình của bạn nhận dữ liệu qua tham số hàm:

• Dòng đầu chứa \(N,Q\).
• Dòng thứ hai chứa \(A_0,A_1,\ldots,A_{N-1}\).
• Dòng thứ \(3+j\) chứa \(X_j,V_j\), với \(0 \le j \le Q-1\).

Dữ liệu ra

Trình chấm mẫu in mảng do countScans trả về: dòng thứ \(1+j\) chứa \(S_j\), với \(0 \le j \le Q-1\).

Ràng buộc

• \(1 \le N \le 500000\); \(1 \le Q \le 500000\).
• \(1 \le A_i \le 1000000000\) với \(0 \le i \le N-1\).
• \(0 \le X_j \le N-1\) và \(1 \le V_j \le 1000000000\) với \(0 \le j \le Q-1\).
• Giới hạn thời gian: \(5\) giây. Giới hạn bộ nhớ: \(512\) MB.

Phân nhóm

1. \(17\) điểm: Giới hạn \(N\): \(1 \le N \le 2000\); Giới hạn \(Q\): \(1 \le Q \le 2000\); Giới hạn giá trị: \(1 \le A_i,V_j \le 1000000000\)
2. \(21\) điểm: Giới hạn \(N\): \(1 \le N \le 8000\); Giới hạn \(Q\): \(1 \le Q \le 8000\); Giới hạn giá trị: \(1 \le A_i,V_j \le 1000000000\)
3. \(22\) điểm: Giới hạn \(N\): \(1 \le N \le 50000\); Giới hạn \(Q\): \(1 \le Q \le 50000\); Giới hạn giá trị: \(1 \le A_i,V_j \le 100\)
4. \(40\) điểm: Giới hạn \(N\): \(1 \le N \le 500000\); Giới hạn \(Q\): \(1 \le Q \le 500000\); Giới hạn giá trị: \(1 \le A_i,V_j \le 1000000000\)

Các điều kiện trên áp dụng cho mọi chỉ số hợp lệ \(0 \le i \le N-1\) và \(0 \le j \le Q-1\).

Ví dụ giao tiếp

Cho \(N=4\), \(A=\{1,2,3,4\}\) và \(Q=2\) truy vấn với \(X=\{0,2\}\), \(V=\{3,1\}\).

Sau truy vấn thứ nhất, thay \(A_0\) bằng \(3\), ta có \(A=\{3,2,3,4\}\). Sau truy vấn thứ hai, thay \(A_2\) bằng \(1\), ta có \(A=\{3,2,1,4\}\).

Với dãy \(\{3,2,3,4\}\), dãy chưa được sắp xếp nên bắt đầu lượt thứ nhất. Vì \(A_0>A_1\), đổi chỗ chúng để được \(\{2,3,3,4\}\). Vì \(A_1 \le A_2\) và \(A_2 \le A_3\), không có lần đổi chỗ nào khác. Dãy đã không giảm, nên thuật toán kết thúc sau \(1\) lượt.

Với dãy \(\{3,2,1,4\}\), trong lượt thứ nhất, đổi chỗ \(A_0,A_1\) để được \(\{2,3,1,4\}\), rồi đổi chỗ \(A_1,A_2\) để được \(\{2,1,3,4\}\). Không đổi chỗ \(A_2,A_3\) vì \(A_2 \le A_3\). Dãy vẫn chưa được sắp xếp, nên bắt đầu lượt thứ hai: đổi chỗ \(A_0,A_1\) để được \(\{1,2,3,4\}\); không đổi chỗ hai cặp còn lại vì chúng đã đúng thứ tự. Dãy đã không giảm, nên thuật toán kết thúc sau \(2\) lượt.

Nguồn

JOI Open 2018 - Bubble Sort 2, đề tiếng Anh, thông báo cài đặt và gói mã mẫu chính thức. Đề bài của Ban tổ chức Olympic Tin học Nhật Bản.

Con trai bạn, JOI, thích nuôi thú cưng. Trong vườn nhà có \(N\) căn chuồng, được đánh số từ \(1\) đến \(N\), mỗi chuồng chứa tối đa một con vật. Có \(N-1\) lối đi hai chiều nối các chuồng, và từ một chuồng bất kỳ đều có thể đi đến mọi chuồng khác bằng các lối đi này.

JOI muốn nuôi cả mèo và chó, nhưng lo rằng chúng sẽ đánh nhau. Với mỗi trạng thái của khu vườn, trong đó mỗi chuồng có một con mèo, một con chó hoặc không có con vật nào, JOI định nghĩa mức độ nguy hiểm là số lối đi ít nhất cần chặn sao cho không có con mèo nào có thể gặp bất kỳ con chó nào bằng cách di chuyển theo các lối đi chưa bị chặn.

Ban đầu, tất cả các chuồng đều trống. JOI lập kế hoạch sử dụng khu vườn trong \(Q\) ngày. Kế hoạch của mỗi ngày là một trong ba việc:

• Đưa một con mèo mới vào chuồng \(v\) đang trống.
• Đưa một con chó mới vào chuồng \(v\) đang trống.
• Cho người hàng xóm con vật đang ở chuồng \(v\), khiến chuồng đó trở thành trống.

Là cha hoặc mẹ của JOI, bạn cần kiểm tra mức độ nguy hiểm của kế hoạch. Hãy tìm mức độ nguy hiểm của khu vườn sau khi thực hiện kế hoạch của từng ngày.

Cài đặt

Với C++, khai báo #include "catdog.h" và cài đặt bốn hàm sau:

void initialize(int N, std::vector<int> A, std::vector<int> B);
int cat(int v);
int dog(int v);
int neighbor(int v);

Đầu tiên, trình chấm gọi initialize(N, A, B) để cung cấp thông tin khu vườn. N là số chuồng. A và B là hai mảng độ dài \(N-1\); với mỗi \(0 \le i \le N-2\), có một lối đi giữa chuồng A[i] và chuồng B[i]. Đảm bảo có thể đi giữa hai chuồng bất kỳ bằng các lối đi.

Sau đó, lần lượt theo thứ tự thời gian của \(Q\) ngày, trình chấm gọi một trong các hàm:

• cat(v): đưa một con mèo mới vào chuồng \(v\) đang trống.
• dog(v): đưa một con chó mới vào chuồng \(v\) đang trống.
• neighbor(v): con vật đang ở chuồng \(v\) rời đi.

Mỗi hàm trong ba hàm này phải trả về mức độ nguy hiểm sau thay đổi của ngày tương ứng. Các thay đổi do những lần gọi hàm gây ra được giữ lại cho các ngày sau. Việc tính số lối đi cần chặn không làm thay đổi các lối đi của khu vườn.

Trên LQDOJ, nộp đúng một tệp C++ cài đặt các hàm theo chữ ký trên. Có thể cài đặt thêm các hàm phụ. Chương trình không được đọc đầu vào chuẩn, ghi đầu ra chuẩn hoặc tương tác với bất kỳ tệp nào khác; được phép ghi ra luồng lỗi chuẩn. Gói đính kèm chính thức vẫn được giữ để tham khảo, nhưng trình chấm của bài này chỉ hỗ trợ C++. Thông báo kỳ thi gốc quy định tối đa \(50\) lần nộp cho mỗi bài.

Dữ liệu vào

Trình chấm mẫu đọc dữ liệu theo định dạng sau; chương trình của bạn nhận dữ liệu qua các lần gọi hàm:

• Dòng đầu chứa \(N\).
• Dòng thứ \(2+i\) chứa \(A_i,B_i\), với \(0 \le i \le N-2\).
• Dòng thứ \(N+1\) chứa \(Q\).
• Dòng thứ \(N+2+j\) chứa \(T_j,v_j\), với \(0 \le j \le Q-1\).

Ở ngày thứ \(j+1\), trình chấm gọi cat(v_j) nếu \(T_j=1\), dog(v_j) nếu \(T_j=2\), hoặc neighbor(v_j) nếu \(T_j=3\).

Dữ liệu ra

Gọi \(D_j\) là giá trị trả về của hàm được gọi ở ngày thứ \(j+1\). Trình chấm mẫu in \(D_j\) trên dòng thứ \(1+j\), với \(0 \le j \le Q-1\).

Ràng buộc

• \(1 \le N \le 100000\); \(1 \le Q \le 100000\).
• Các chuồng được đánh số từ \(1\) đến \(N\); có \(N-1\) lối đi hai chiều và có thể đi giữa hai chuồng bất kỳ.
• Mỗi chuồng có tối đa một con vật. Mỗi thao tác thêm con vật được thực hiện trên một chuồng trống; mỗi thao tác cho con vật đi được thực hiện trên một chuồng đang có con vật.
• Giới hạn thời gian: \(3\) giây. Giới hạn bộ nhớ: \(512\) MB.

Phân nhóm

1. \(8\) điểm: Giới hạn \(N\): \(1 \le N \le 15\); Giới hạn \(Q\): \(1 \le Q \le 100\)
2. \(30\) điểm: Giới hạn \(N\): \(1 \le N \le 1000\); Giới hạn \(Q\): \(1 \le Q \le 1000\)
3. \(62\) điểm: Giới hạn \(N\): \(1 \le N \le 100000\); Giới hạn \(Q\): \(1 \le Q \le 100000\)

Ví dụ giao tiếp

Có \(5\) chuồng và \(4\) lối đi: giữa chuồng \(1\) và \(2\), giữa chuồng \(2\) và \(3\), giữa chuồng \(2\) và \(4\), giữa chuồng \(4\) và \(5\).

Ban đầu, giả sử JOI đã đưa một con mèo vào chuồng \(3\) và một con chó vào chuồng \(5\). Chặn lối đi giữa chuồng \(2\) và \(4\) sẽ ngăn mèo và chó gặp nhau. Mức độ nguy hiểm lúc này là \(1\).

Tiếp theo, giả sử JOI đưa thêm một con mèo vào chuồng \(2\) và một con chó vào chuồng \(1\). Chặn lối đi giữa chuồng \(2\) và \(4\), cùng với lối đi giữa chuồng \(1\) và \(2\), sẽ ngăn mèo và chó gặp nhau. Mức độ nguy hiểm lúc này là \(2\).

Cuối cùng, giả sử JOI cho người hàng xóm con mèo ở chuồng \(2\). Lúc này chỉ cần chặn lối đi giữa chuồng \(2\) và \(3\), nên mức độ nguy hiểm là \(1\).

Nguồn

JOI Open 2018 - Cats or Dogs, đề tiếng Anh, thông báo cài đặt và gói mã mẫu chính thức. Đề bài của Ban tổ chức Olympic Tin học Nhật Bản.

Có \(N\) thị trấn nằm dọc theo một thung lũng sâu và thẳng ở đất nước JOI. Các thị trấn được đánh số \(0,1,\ldots,N-1\) theo thứ tự khoảng cách tăng dần từ biển.

Ông I, chủ tịch Ủy ban Khoa học của đất nước JOI, dự định xây dựng và duy trì các cáp liên lạc hai chiều giữa các thị trấn. Ban đầu chưa có cáp nào. Ông I có kế hoạch cho \(C\) ngày. Kế hoạch của ngày thứ \(i+1\), với \(0 \le i \le C-1\), được mô tả bởi ba số nguyên \(T_i,X_i,Y_i\):

• Nếu \(T_i=0\), xây một cáp nối thị trấn \(X_i\) và thị trấn \(Y_i\). Đảm bảo vào đầu ngày thứ \(i+1\) chưa có cáp nối hai thị trấn này.
• Nếu \(T_i=1\), tháo cáp nối thị trấn \(X_i\) và thị trấn \(Y_i\). Đảm bảo vào đầu ngày thứ \(i+1\) có cáp nối hai thị trấn này.

Ở đất nước JOI thường xảy ra sạt lở vách núi. Nếu sạt lở xảy ra giữa thị trấn \(x\) và thị trấn \(x+1\), với \(0 \le x \le N-2\), mọi cáp nối một thị trấn có số hiệu không lớn hơn \(x\) với một thị trấn có số hiệu không nhỏ hơn \(x+1\) đều không sử dụng được. Khi đó, cần chọn một số thị trấn để lắp trạm gốc, sao cho từ bất kỳ thị trấn nào cũng có thể đến được một trạm gốc bằng các cáp còn sử dụng được.

Ông I có \(Q\) câu hỏi. Câu hỏi thứ \(j+1\) được mô tả bởi hai số nguyên \(W_j,P_j\): nếu sạt lở xảy ra giữa thị trấn \(P_j\) và thị trấn \(P_j+1\) vào cuối ngày thứ \(W_j+1\), thì cần lắp ít nhất bao nhiêu trạm gốc?

Hãy viết chương trình trả lời các câu hỏi này. Mỗi câu hỏi xét riêng một tình huống sạt lở đối với mạng cáp sau các thao tác xây hoặc tháo cáp đến ngày được hỏi; các tình huống sạt lở không làm thay đổi kế hoạch cho những câu hỏi khác.

Cài đặt

Với C++, khai báo #include "collapse.h" và cài đặt hàm:

std::vector<int> simulateCollapse(
    int N,
    std::vector<int> T,
    std::vector<int> X,
    std::vector<int> Y,
    std::vector<int> W,
    std::vector<int> P
);

• N là số thị trấn.
• T, X, Y là ba mảng độ dài \(C\). Với \(0 \le i \le C-1\), T[i], X[i], Y[i] mô tả kế hoạch của ngày thứ \(i+1\).
• W, P là hai mảng độ dài \(Q\). Với \(0 \le j \le Q-1\), W[j], P[j] mô tả câu hỏi thứ \(j+1\).
• Hàm trả về mảng số nguyên D độ dài \(Q\), trong đó D[j] là câu trả lời cho câu hỏi thứ \(j+1\).

Trên LQDOJ, nộp đúng một tệp C++ cài đặt các hàm theo chữ ký trên. Có thể cài đặt thêm các hàm phụ. Chương trình không được đọc đầu vào chuẩn, ghi đầu ra chuẩn hoặc tương tác với bất kỳ tệp nào khác; được phép ghi ra luồng lỗi chuẩn. Gói đính kèm chính thức vẫn được giữ để tham khảo, nhưng trình chấm của bài này chỉ hỗ trợ C++. Thông báo kỳ thi gốc quy định tối đa \(50\) lần nộp cho mỗi bài.

Dữ liệu vào

Trình chấm mẫu đọc dữ liệu theo định dạng sau; chương trình của bạn nhận dữ liệu qua tham số hàm:

• Dòng đầu chứa \(N,C,Q\).
• Dòng thứ \(2+i\) chứa \(T_i,X_i,Y_i\), với \(0 \le i \le C-1\).
• Dòng thứ \(2+C+j\) chứa \(W_j,P_j\), với \(0 \le j \le Q-1\).

Dữ liệu ra

Trình chấm mẫu in mảng do simulateCollapse trả về: dòng thứ \(1+j\) chứa \(D_j\), với \(0 \le j \le Q-1\).

Ràng buộc

• \(2 \le N \le 100000\).
• \(1 \le C \le 100000\); \(1 \le Q \le 100000\).
• Với mọi \(0 \le i \le C-1\): \(T_i \in \{0,1\}\), \(0 \le X_i,Y_i \le N-1\), \(X_i \ne Y_i\).
• Với mọi \(0 \le j \le Q-1\): \(0 \le W_j \le C-1\), \(0 \le P_j \le N-2\).
• Các thao tác xây và tháo cáp luôn hợp lệ như mô tả ở trên.
• Giới hạn thời gian: \(6\) giây. Giới hạn bộ nhớ: \(512\) MB.

Phân nhóm

1. \(5\) điểm: Giới hạn \(N\): \(2 \le N \le 5000\); Giới hạn \(C,Q\): \(1 \le C,Q \le 5000\); Điều kiện bổ sung: Không có.
2. \(30\) điểm: Giới hạn \(N\): \(2 \le N \le 100000\); Giới hạn \(C,Q\): \(1 \le C,Q \le 100000\); Điều kiện bổ sung: Tất cả \(P_j\), với \(0 \le j \le Q-1\), bằng nhau.
3. \(30\) điểm: Giới hạn \(N\): \(2 \le N \le 100000\); Giới hạn \(C,Q\): \(1 \le C,Q \le 100000\); Điều kiện bổ sung: \(T_i=0\) với mọi \(0 \le i \le C-1\).
4. \(35\) điểm: Giới hạn \(N\): \(2 \le N \le 100000\); Giới hạn \(C,Q\): \(1 \le C,Q \le 100000\); Điều kiện bổ sung: Không có.

Ví dụ giao tiếp

Xét \(5\) thị trấn. Ký hiệu \((x,y)\) là cáp nối thị trấn \(x\) và thị trấn \(y\).

Giả sử có bốn cáp \((0,1)\), \((1,3)\), \((2,4)\), \((4,0)\) và sạt lở xảy ra giữa thị trấn \(1\) và thị trấn \(2\). Các cáp \((1,3)\) và \((4,0)\) không sử dụng được, nên chỉ còn cáp \((0,1)\) và \((2,4)\). Có thể lắp trạm gốc ở các thị trấn \(0\), \(2\) và \(3\). Số trạm gốc ít nhất cần lắp là \(3\).

Trong một tình huống khác, giả sử có sáu cáp \((0,1)\), \((0,3)\), \((1,2)\), \((2,4)\), \((4,0)\), \((4,3)\) và sạt lở xảy ra giữa thị trấn \(3\) và thị trấn \(4\). Các cáp \((2,4)\), \((4,0)\) và \((4,3)\) không sử dụng được, nên chỉ còn cáp \((0,1)\), \((0,3)\) và \((1,2)\). Có thể lắp trạm gốc ở thị trấn \(0\) và thị trấn \(4\). Số trạm gốc ít nhất cần lắp là \(2\).

Nguồn

JOI Open 2018 - Collapse, đề tiếng Anh, thông báo cài đặt và gói mã mẫu chính thức. Đề bài của Ban tổ chức Olympic Tin học Nhật Bản.

Xylophone là một nhạc cụ được chơi bằng cách gõ vào các thanh gỗ. Mỗi thanh luôn phát ra cùng một cao độ, nên đàn gồm nhiều thanh có cao độ khác nhau.

JOI mua một cây đàn gồm \(N\) thanh gỗ xếp thành một hàng, được đánh số từ \(1\) đến \(N\) từ trái sang phải. Thanh thứ \(i\) phát ra âm có cao độ \(A_i\), với \(1 \le A_i \le N\). Hai thanh khác nhau có cao độ khác nhau. JOI biết rằng thanh có cao độ thấp nhất nằm bên trái thanh có cao độ cao nhất.

JOI chưa biết cao độ của từng thanh và muốn xác định chúng. JOI có thính giác đặc biệt: khi nhiều âm thanh vang lên cùng lúc, cậu có thể nhận biết hiệu giữa cao độ cao nhất và thấp nhất. Với hai số nguyên \(s,t\) thỏa mãn \(1 \le s \le t \le N\), JOI có thể gõ đồng thời tất cả các thanh từ \(s\) đến \(t\), qua đó biết hiệu giữa giá trị lớn nhất và nhỏ nhất trong \(A_s,A_{s+1},\ldots,A_t\).

Hãy xác định cao độ của tất cả các thanh bằng không quá \(10000\) lần gõ như vậy.

Cài đặt

Với C++, khai báo #include "xylophone.h" và cài đặt hàm:

void solve(int N);

N là số thanh gỗ. Hàm solve được gọi đúng một lần cho mỗi bộ dữ liệu. Chương trình có thể gọi hai hàm do trình chấm cung cấp:

int query(int s, int t);
void answer(int i, int a);

query(s, t) trả về hiệu giữa cao độ lớn nhất và nhỏ nhất của các thanh có số hiệu từ \(s\) đến \(t\), kể cả hai đầu mút. Phải có \(1 \le s \le t \le N\). Không được gọi query quá \(10000\) lần. Vi phạm một trong các điều kiện này sẽ bị chấm Wrong Answer.

answer(i, a) thông báo rằng cao độ của thanh thứ \(i\) là \(a\), tức là \(A_i=a\). Phải có \(1 \le i \le N\). Không được gọi hàm này nhiều hơn một lần với cùng một giá trị \(i\), và phải gọi đúng \(N\) lần trước khi solve kết thúc. Vi phạm một trong các điều kiện này, hoặc thông báo sai cao độ của bất kỳ thanh nào, sẽ bị chấm Wrong Answer.

Trên LQDOJ, nộp đúng một tệp C++ cài đặt hàm theo chữ ký trên. Có thể cài đặt thêm các hàm phụ. Chương trình không được đọc đầu vào chuẩn, ghi đầu ra chuẩn hoặc tương tác với bất kỳ tệp nào khác; được phép ghi ra luồng lỗi chuẩn. Gói đính kèm chính thức vẫn được giữ để tham khảo, nhưng trình chấm của bài này chỉ hỗ trợ C++. Thông báo kỳ thi gốc quy định tối đa \(50\) lần nộp cho mỗi bài.

Dữ liệu vào

Trình chấm mẫu đọc dữ liệu theo định dạng sau; chương trình của bạn không được đọc trực tiếp dữ liệu này:

• Dòng đầu chứa \(N\).
• Dòng thứ \(1+i\) chứa \(A_i\), với \(1 \le i \le N\).

Dữ liệu ra

Nếu khi solve kết thúc, chương trình đã trả lời đúng cao độ của mọi thanh, trình chấm mẫu in Accepted : Q, trong đó \(Q\) là số lần gọi query. Nếu chương trình bị chấm sai, trình chấm mẫu in Wrong Answer.

Ràng buộc

• \(2 \le N \le 5000\).
• \(1 \le A_i \le N\) với mọi \(1 \le i \le N\).
• \(A_i \ne A_j\) với mọi \(1 \le i<j \le N\).
• Với hai chỉ số \(i,j\) thỏa mãn \(A_i=1\) và \(A_j=N\), luôn có \(i<j\).
• Không quá \(10000\) lần gọi query trong mỗi bộ dữ liệu.
• Giới hạn thời gian: \(2\) giây. Giới hạn bộ nhớ: \(256\) MB.

Phân nhóm

1. \(11\) điểm: \(2 \le N \le 100\)
2. \(36\) điểm: \(2 \le N \le 1000\)
3. \(53\) điểm: \(2 \le N \le 5000\)

Mọi nhóm đều thỏa mãn các điều kiện về cao độ và thứ tự vị trí của thanh thấp nhất, cao nhất nêu trên, cùng giới hạn \(10000\) lần gọi query.

Ví dụ giao tiếp

Với \(N=5\) và \((A_1,A_2,A_3,A_4,A_5)=(2,1,5,3,4)\), một trình tự tương tác là:

Nguồn

JOI Open 2018 - Xylophone, đề tiếng Anh, thông báo cài đặt và gói mã mẫu chính thức. Đề bài của Ban tổ chức Olympic Tin học Nhật Bản.