JOI 2020 - Trại huấn luyện mùa xuân - Ngày 2

Trong sở thú JOI có \(2N\) con tắc kè hoa, được đánh số từ \(1\) đến \(2N\). Trong đó, \(N\) con có giới tính X và \(N\) con còn lại có giới tính Y.

Mỗi con có một màu gốc. Các màu gốc có những tính chất sau:

• \(N\) con có giới tính X có màu gốc đôi một khác nhau.
• Với mỗi con có giới tính X, có đúng một con có giới tính Y mang cùng màu gốc với nó.

Sở thú JOI đang bước vào mùa tình yêu. Mỗi con tắc kè hoa yêu một con khác. Những mối quan hệ này có các tính chất sau:

• Mỗi con yêu đúng một con khác giới tính với mình.
• Mỗi con và con mà nó yêu có màu gốc khác nhau.
• Không có hai con cùng yêu một con.

Bạn có thể tập hợp một số con tắc kè hoa để tổ chức một cuộc gặp. Với mỗi con \(s\) tham dự cuộc gặp, gọi \(t\) là con mà \(s\) yêu. Màu da của \(s\) được xác định như sau:

• Nếu \(t\) tham dự cuộc gặp, màu da của \(s\) là màu gốc của \(t\).
• Nếu \(t\) không tham dự cuộc gặp, màu da của \(s\) là màu gốc của chính \(s\).

Màu da của một con có thể thay đổi giữa các cuộc gặp. Trong mỗi cuộc gặp do bạn tổ chức, bạn có thể biết số màu da khác nhau của những con tham dự.

Cho số lượng tắc kè hoa, hãy xác định tất cả các cặp có cùng màu gốc bằng cách tổ chức không quá \(20\,000\) cuộc gặp.

Giao diện tương tác

Bạn cần nộp tệp chameleon.cpp, khai báo sử dụng chameleon.h và cài đặt hàm sau:

void Solve(int N);

Hàm được gọi đúng một lần cho mỗi bộ dữ liệu. Tham số \(N\) là số con có giới tính X, bằng một nửa tổng số con.

Chương trình của bạn có thể gọi các hàm sau:

int Query(const std::vector<int> &p);
void Answer(int a, int b);

Mỗi lần gọi Query(p) tổ chức một cuộc gặp với danh sách các con tham dự là p. Hàm trả về số màu da khác nhau trong cuộc gặp đó.

• Mỗi phần tử của p phải là số nguyên từ \(1\) đến \(2N\). Vi phạm điều kiện này sẽ nhận Wrong Answer [1].
• Các phần tử của p phải đôi một khác nhau. Vi phạm điều kiện này sẽ nhận Wrong Answer [2].
• Không được gọi Query quá \(20\,000\) lần. Vi phạm điều kiện này sẽ nhận Wrong Answer [3].

Danh sách p có thể rỗng; một lần gọi như vậy vẫn được tính là một lần gọi Query và trả về \(0\).

Mỗi lần gọi Answer(a, b) thông báo rằng con \(a\) và con \(b\) có cùng màu gốc.

• Phải có \(1 \le a \le 2N\) và \(1 \le b \le 2N\). Vi phạm điều kiện này sẽ nhận Wrong Answer [4].
• Mỗi chỉ số chỉ được xuất hiện một lần trong toàn bộ các tham số của tất cả lời gọi Answer; hai chỉ số trong cùng một lời gọi cũng phải khác nhau. Vi phạm điều kiện này sẽ nhận Wrong Answer [5].
• Nếu \(a\) và \(b\) có màu gốc khác nhau, chương trình nhận Wrong Answer [6].
• Phải gọi Answer đúng \(N\) lần. Khi Solve kết thúc, nếu số lần gọi khác \(N\), chương trình nhận Wrong Answer [7].

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

Dữ liệu vào

Dữ liệu sau dành cho trình chấm mẫu grader.cpp. Trình chấm mẫu và mã nguồn mẫu được cung cấp trong gói tệp hỗ trợ chính thức.

N
Y_1 ... Y_{2N}
C_1 ... C_{2N}
L_1 ... L_{2N}

Với \(1 \le i \le 2N\):

• \(Y_i\) biểu diễn giới tính của con \(i\): \(0\) là X và \(1\) là Y.
• \(C_i\) là màu gốc của con \(i\), được biểu diễn bởi một số nguyên từ \(1\) đến \(N\).
• \(L_i\) là chỉ số của con mà con \(i\) yêu.

Chương trình của bạn nhận thông tin qua giao diện tương tác ở trên, không trực tiếp đọc các mảng này.

Dữ liệu ra

Chương trình của bạn thông báo các cặp bằng Answer.

Khi chương trình kết thúc bình thường, trình chấm mẫu ghi kết quả ra đầu ra chuẩn như sau:

• Nếu câu trả lời đúng, trình chấm mẫu ghi số lần gọi Query, theo dạng như Accepted: 100.
• Nếu câu trả lời sai, trình chấm mẫu ghi loại lỗi, theo dạng như Wrong Answer [1].

Nếu chương trình mắc nhiều loại lỗi, trình chấm mẫu chỉ thông báo một loại.

Ràng buộc

Các dữ liệu thỏa mãn những điều kiện sau, với \(Y,C,L\) được định nghĩa trong phần dữ liệu vào cho trình chấm mẫu:

• \(2 \le N \le 500\).
• \(0 \le Y_i \le 1\) với \(1 \le i \le 2N\).
• \(1 \le C_i \le N\) với \(1 \le i \le 2N\).
• Với mỗi \(j\) (\(1 \le j \le N\)), có đúng một \(i\) (\(1 \le i \le 2N\)) thỏa mãn \(Y_i=0\) và \(C_i=j\).
• Với mỗi \(j\) (\(1 \le j \le N\)), có đúng một \(i\) (\(1 \le i \le 2N\)) thỏa mãn \(Y_i=1\) và \(C_i=j\).
• \(1 \le L_i \le 2N\) với \(1 \le i \le 2N\).
• \(Y_i \ne Y_{L_i}\) với \(1 \le i \le 2N\).
• \(C_i \ne C_{L_i}\) với \(1 \le i \le 2N\).
• \(L_k \ne L_l\) với \(1 \le k < l \le 2N\).

Phân nhóm

1. (4 điểm) \(L_{L_i}=i\) với \(1 \le i \le 2N\).
2. (20 điểm) \(N \le 7\).
3. (20 điểm) \(N \le 50\).
4. (20 điểm) \(Y_i=0\) với \(1 \le i \le N\).
5. (36 điểm) Không có ràng buộc bổ sung.

Ví dụ giao tiếp

4
1 0 1 0 0 1 1 0
4 4 1 2 1 2 3 3
4 3 8 7 6 5 2 1

Với dữ liệu trên, một quá trình tương tác có thể diễn ra như sau. Trình chấm gọi Solve(4), sau đó chương trình thực hiện các lời gọi theo đúng thứ tự trong bảng.

4
1 1 1 0 0 1 0 0
3 1 4 3 1 2 2 4
5 7 4 3 1 8 2 6

Đây là tệp sample-02.txt trong gói dữ liệu chính thức. Dữ liệu này thỏa mãn ràng buộc của nhóm \(1\).

4
0 0 0 0 1 1 1 1
4 3 2 1 2 3 4 1
6 8 7 5 2 3 4 1

Đây là tệp sample-03.txt trong gói dữ liệu chính thức. Dữ liệu này thỏa mãn ràng buộc của nhóm \(4\).

Nguồn

Bản dịch tiếng Việt từ đề chính thức bằng tiếng Anh của Ủy ban Olympic Tin học Nhật Bản, JOI 2019/2020, Trại huấn luyện mùa xuân, ngày thi thứ 2. Các tệp ví dụ bổ sung lấy từ gói dữ liệu chính thức. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.

Joitter là một mạng xã hội đang thịnh hành, nơi bạn có thể chia sẻ những kỷ niệm với bạn bè.

Trên Joitter, người dùng có thể theo dõi những người dùng khác. Chẳng hạn, khi người dùng \(a\) theo dõi người dùng \(b\), \(a\) có thể đọc các bài đăng của \(b\) trên dòng thời gian. Khi đó, \(b\) có thể theo dõi lại \(a\) hoặc không. Tuy nhiên, một người dùng không thể theo dõi chính mình và không thể theo dõi cùng một người dùng khác nhiều hơn một lần.

Có \(N\) người dùng, được đánh số từ \(1\) đến \(N\), vừa bắt đầu sử dụng Joitter. Ban đầu, không ai theo dõi ai.

Trong \(M\) ngày tiếp theo, vào ngày thứ \(i\) (\(1 \le i \le M\)), người dùng \(A_i\) bắt đầu theo dõi người dùng \(B_i\).

Ban quản lý Joitter dự định tổ chức một sự kiện giao lưu đúng một lần trong \(M\) ngày này. Sự kiện diễn ra như sau:

1. Chọn một người dùng, gọi là \(x\).
2. Chọn một người dùng mà \(x\) đang theo dõi, gọi là \(y\).
3. Chọn một người dùng \(z\) thỏa mãn: \(z\) khác \(x\), \(x\) chưa theo dõi \(z\), \(y\) đang theo dõi \(z\), và \(z\) đang theo dõi \(y\).
4. Cho \(x\) theo dõi \(z\).
5. Lặp lại các bước trên cho đến khi không thể chọn được bộ ba \((x,y,z)\) nào nữa.

Ban quản lý chưa quyết định ngày tổ chức sự kiện. Vì vậy, với mỗi \(i\) (\(1 \le i \le M\)), họ muốn biết giá trị lớn nhất của tổng số người được theo dõi bởi từng người dùng sau sự kiện, nếu sự kiện được tổ chức ngay sau khi \(A_i\) theo dõi \(B_i\) vào ngày thứ \(i\). Sự kiện được giả sử là kết thúc trước hành động theo dõi vào ngày tiếp theo.

Các thời điểm tổ chức được xét riêng biệt; trong mỗi trường hợp chỉ có một sự kiện giao lưu. Cho số người dùng và các hành động theo dõi trong \(M\) ngày, hãy tính các giá trị lớn nhất nói trên.

Dữ liệu vào

Đọc từ đầu vào chuẩn theo dạng sau. Tất cả các giá trị đều là số nguyên.

N M
A_1 B_1
...
A_M B_M

Dữ liệu ra

In ra \(M\) dòng. Dòng thứ \(i\) (\(1 \le i \le M\)) chứa giá trị lớn nhất của tổng số người được theo dõi bởi từng người dùng sau sự kiện giao lưu, nếu sự kiện được tổ chức ngay sau hành động theo dõi của ngày thứ \(i\).

Ràng buộc

• \(2 \le N \le 100\,000\).
• \(1 \le M \le 300\,000\).
• \(1 \le A_i \le N\) với \(1 \le i \le M\).
• \(1 \le B_i \le N\) với \(1 \le i \le M\).
• \(A_i \ne B_i\) với \(1 \le i \le M\).
• \((A_i,B_i) \ne (A_j,B_j)\) với \(1 \le i < j \le M\).

Phân nhóm

1. (1 điểm) \(N \le 50\).
2. (16 điểm) \(N \le 2000\).
3. (83 điểm) Không có ràng buộc bổ sung.

Ví dụ

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

1
2
4
4
5
9

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

1
2
3
4
5
7
11
17
25
30

Nguồn

Bản dịch tiếng Việt từ đề chính thức bằng tiếng Anh của Ủy ban Olympic Tin học Nhật Bản, JOI 2019/2020, Trại huấn luyện mùa xuân, ngày thi thứ 2. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.

Giáo sư JOI là một chuyên gia hàng đầu về lịch sử Vương quốc IOI. Khi khảo sát một ngôi đền cổ trong vương quốc, ông tìm thấy một khu di tích từng có các cột đá. Ông cũng tìm thấy một tài liệu cổ được cho là do cư dân Vương quốc IOI thời xưa viết lại. Tài liệu mô tả các cột đá như sau:

• Ngay sau khi được dựng lên, có \(2N\) cột đá, được đánh số từ \(1\) đến \(2N\).
• Ngay sau khi được dựng lên, với mỗi \(k\) (\(1 \le k \le N\)), có đúng hai cột đá cao \(k\).
• Đã xảy ra \(N\) trận động đất. Sau mỗi trận, một số cột đá bị sụp một phần và chiều cao giảm đi \(1\). Những cột khác được người xưa bảo vệ nên không bị sụp và giữ nguyên chiều cao.
• Khi xảy ra động đất, với mỗi \(k\) (\(1 \le k \le N\)), người xưa bảo vệ đúng một cột đá cao \(k\). Nếu có nhiều cột cùng cao \(k\) vào thời điểm đó, cột có chỉ số lớn nhất được bảo vệ. Nói cách khác, nếu trước trận động đất cột \(i\) (\(1 \le i \le 2N\)) có chiều cao \(h_i\), thì cột \(i\) được bảo vệ khi và chỉ khi \(h_i \ge 1\) và \(h_j \ne h_i\) với mọi \(j>i\).
• Sau \(N\) trận động đất, còn lại \(N\) cột đá, tức là có đúng \(N\) cột có chiều cao ít nhất \(1\).

Giáo sư JOI cho rằng việc khôi phục chiều cao ban đầu của \(2N\) cột đá sẽ là một phát hiện lớn. Sau khi khảo sát kỹ hơn, ông xác định được các chỉ số của những cột còn lại sau \(N\) trận động đất là \(A_1,A_2,\ldots,A_N\).

Giáo sư muốn biết có bao nhiêu cách gán chiều cao ban đầu cho \(2N\) cột đá phù hợp với tài liệu cổ và thông tin đã tìm được. Là học trò của giáo sư, bạn được giao viết chương trình tính số cách đó, lấy số dư khi chia cho \(1\,000\,000\,007\).

Dữ liệu vào

Đọc từ đầu vào chuẩn theo dạng sau. Tất cả các giá trị đều là số nguyên.

N
A_1 ... A_N

Dữ liệu ra

In ra một dòng chứa số dư của số cách gán chiều cao ban đầu thỏa mãn yêu cầu khi chia cho \(1\,000\,000\,007\).

Ràng buộc

• \(1 \le N \le 600\).
• \(1 \le A_i \le 2N\) với \(1 \le i \le N\).
• \(A_i < A_{i+1}\) với \(1 \le i \le N-1\).

Phân nhóm

1. (6 điểm) \(N \le 13\).
2. (52 điểm) \(N \le 60\).
3. (42 điểm) Không có ràng buộc bổ sung.

Ví dụ

3
3 4 6

5

1
1

0

10
5 8 9 13 15 16 17 18 19 20

147003663

Nguồn

Bản dịch tiếng Việt từ đề chính thức bằng tiếng Anh của Ủy ban Olympic Tin học Nhật Bản, JOI 2019/2020, Trại huấn luyện mùa xuân, ngày thi thứ 2. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.