BOI 2022 - Ngày 1

Dù những ngày làm kẻ trộm tranh đã lùi xa, bạn vẫn không mất đi niềm yêu thích nghệ thuật đương đại. Đáng tiếc là gần đây bạn quá bận chuẩn bị cho BOI nên không còn nắm được thứ hạng theo giá trị của \(N\) bộ sưu tập nghệ thuật đương đại nổi tiếng nhất, được đánh số từ \(1\) đến \(N\). Hỏi thẳng người khác thì thật đáng ngượng, vì vậy bạn phải tìm cách khác: đăng các bảng xếp hạng ẩn danh trên mạng.

Bạn sẽ lặp lại việc sau: đoán thứ hạng của \(N\) bộ sưu tập theo giá trị, từ đắt nhất đến rẻ nhất, đăng bảng xếp hạng lên một trang web, rồi chờ chủ các bộ sưu tập phàn nàn trong phần bình luận. Vì không muốn đọc từng bình luận, bạn chỉ đếm tổng số lời phàn nàn nhận được. May thay, hành vi của các chủ sở hữu rất nhất quán: mỗi người phàn nàn đúng một lần cho mỗi bộ sưu tập bị bạn xếp cao hơn bộ sưu tập của họ dù trong thứ hạng thật thì không phải vậy. Không ai phàn nàn về những bộ sưu tập bị bạn xếp thấp hơn bộ sưu tập của họ một cách sai lầm. Giá trị của các bộ sưu tập đôi một khác nhau.

“Độc giả còn thích: 13 ứng dụng GÂY SỐC của thuật toán Dijkstra mà các nhà khoa học máy tính không muốn bạn biết!”

Tuy nhiên, mỗi lần đăng bảng xếp hạng đều có nguy cơ làm lộ danh tính của bạn — chắc chắn là do văn phong đặc trưng, chứ không phải vì bạn hay vô tình ký tên mình vào bài viết. Vì vậy, bạn chỉ muốn đăng tối đa \(4\,000\) bảng xếp hạng dự đoán trước khi tìm ra thứ hạng chính xác. Hãy viết chương trình giúp bạn quyết định nên đăng những bảng xếp hạng nào.

Giao tiếp

Đây là bài tương tác thông qua hàm. Bạn phải cài đặt hàm sau; với mỗi bộ dữ liệu, trình chấm gọi hàm đúng một lần, trong đó \(N\) là số bộ sưu tập:

void solve(int N);

Trong solve, bạn được sử dụng các hàm do trình chấm cung cấp:

int publish(std::vector<int> R);
void answer(std::vector<int> R);

• publish(R) đăng bảng xếp hạng \(R\) lên trang web. \(R\) phải là một hoán vị của các số từ \(1\) đến \(N\), với những bộ sưu tập mà bạn đoán là đắt hơn đứng trước. Hàm trả về số lời phàn nàn nhận được. Bạn được gọi hàm này tối đa \(4\,000\) lần trong mỗi bộ dữ liệu.
• answer(R) thông báo rằng bạn đã tìm được thứ hạng chính xác \(R\), theo cùng định dạng với publish. Bạn phải gọi answer đúng một lần; chương trình sẽ tự động bị kết thúc ngay sau đó.

Nếu một lời gọi không thỏa mãn các điều kiện trên, chương trình bị kết thúc ngay và nhận kết quả Not correct cho bộ dữ liệu tương ứng. Bạn không được ghi ra đầu ra chuẩn hoặc đọc từ đầu vào chuẩn; nếu vi phạm, bạn có thể nhận kết quả Security violation!.

Mã nguồn phải chứa #include "art.h". Bạn cài đặt solve, không viết hàm main.

Biên dịch và chạy thử

Gói đính kèm của bài trên CMS chính thức có art.h, trình chấm mẫu sample_grader.cpp và chương trình mẫu art_sample.cpp. Có thể liên kết bài làm với trình chấm mẫu để chạy thử; hướng dẫn nằm trong sample_grader.cpp. Chẳng hạn, đặt art.cpp, art.h và sample_grader.cpp trong cùng thư mục rồi chạy:

g++ -std=c++17 sample_grader.cpp art.cpp
./a.out

Trình chấm mẫu đọc hai dòng từ đầu vào chuẩn. Dòng đầu chứa \(N\). Dòng thứ hai chứa \(N\) số nguyên cách nhau bởi dấu cách, là thứ hạng chính xác của các bộ sưu tập, theo cùng định dạng với publish và answer. Sau đó, trình chấm gọi solve(N) và ghi nhật ký tất cả các lời gọi hàm trình chấm ra đầu ra chuẩn. Khi kết thúc, nó in một trong các thông báo sau:

• Invalid input.: dữ liệu nhập cho trình chấm không đúng định dạng trên.
• Invalid published ranking.: gọi publish với tham số không hợp lệ.
• Too many published rankings.: gọi publish quá \(4\,000\) lần.
• No answer.: hàm solve kết thúc mà chưa gọi answer.
• Wrong answer.: gọi answer với thứ hạng không đúng.
• Correct: p published ranking(s).: gọi answer với thứ hạng đúng sau \(p\) lần gọi publish.

Các thông báo trên giữ nguyên cách viết trong PDF chính thức. Trình chấm thật chỉ in Not correct khi gặp bất kỳ lỗi nào ở trên, hoặc Correct. Cả trình chấm mẫu lẫn trình chấm thật đều tự động kết thúc chương trình khi có lỗi hoặc sau khi bạn gọi answer. Việc đọc và ghi các luồng chuẩn ở phần chạy thử do trình chấm mẫu thực hiện.

Ràng buộc

• \(2\le N\le4\,000\).
• Giới hạn thời gian: \(3\) giây.
• Giới hạn bộ nhớ: \(512\) MiB.

Phân nhóm

1. \(5\) điểm: \(N\le6\).
2. \(15\) điểm: \(N\le40\).
3. \(15\) điểm: \(N\le250\).
4. \(15\) điểm: \(N\le444\).
5. \(20\) điểm: \(N\le2\,000\).
6. \(30\) điểm: không có ràng buộc thêm.

Ví dụ giao tiếp

Xét \(N=3\), trong đó bộ sưu tập \(1\) đắt nhất, tiếp theo là bộ sưu tập \(3\), còn bộ sưu tập \(2\) rẻ nhất. Trước tiên, trình chấm gọi solve(3). Một quá trình giao tiếp có thể diễn ra như sau; mũi tên chỉ giá trị trả về:

publish({1, 2, 3}) -> 1
publish({2, 3, 1}) -> 3
answer({1, 3, 2})

Lần đăng đầu tiên nhận một lời phàn nàn từ chủ bộ sưu tập \(3\). Lần thứ hai nhận hai lời phàn nàn từ chủ bộ sưu tập \(1\) và một lời phàn nàn từ chủ bộ sưu tập \(3\). Sau đó, bạn tin rằng đã tìm được thứ hạng chính xác và gọi answer({1, 3, 2}); câu trả lời đúng và được chấp nhận.

Thật trùng hợp kỳ lạ! Sau khi xác định được bộ sưu tập nghệ thuật đương đại có giá trị nhất, bạn nhận ra rằng dường như nó nằm đâu đó gần Lübeck. Vì chưa biết vị trí chính xác, bạn muốn thu thập thêm thông tin. May thay, vào ngày bạn đến dự BOI năm nay, cộng đồng nghệ thuật địa phương tổ chức \(N\) sự kiện về nghệ thuật đương đại. Đây có vẻ chính là cơ hội bạn đang chờ đợi.

Để lên kế hoạch tham dự, bạn đánh số các sự kiện từ \(1\) đến \(N\). Sự kiện thứ \(i\) bắt đầu lúc \(S_i\) và kết thúc lúc \(E_i\). Bạn muốn bắt đầu chuyến tham dự ở sự kiện \(s\) và kết thúc ở sự kiện \(e\). Chừng nào chưa tham dự sự kiện \(e\), bạn luôn ở lại sự kiện hiện tại đến khi nó kết thúc, rồi lập tức chuyển sang một sự kiện khác đang diễn ra. Rời đi sớm sẽ thật bất lịch sự, nhưng chẳng ai phàn nàn nếu bạn đến muộn: rõ ràng bạn là một nhà phê bình nghệ thuật quan trọng và bận rộn. Như vậy, bạn có thể chuyển từ sự kiện \(i\) sang sự kiện \(j\) khi và chỉ khi \(S_j\le E_i\le E_j\).

Lịch minh họa vào thứ Năm, ngày 28/4: bài nói chuyện của ông Masterart; triển lãm “Bài tập rác đương đại”; hội thảo thiết kế sô-cô-la hiện đại; lễ trao giải quả trứng Phục sinh đương đại đẹp nhất; khai trương phòng trưng bày; chợ nghệ thuật truyền thống Lübeck; và tiệc tối dành cho các nhà sưu tập nghệ thuật.

Rõ ràng, đổi sự kiện quá thường xuyên sẽ khiến bạn trông đáng ngờ. Vì vậy, bạn muốn biết số lần chuyển sự kiện ít nhất cần thiết để bắt đầu ở \(s\) và kết thúc ở \(e\). Bạn cũng chưa biết lúc nào mình sẽ đến Lübeck và lúc nào phải rời đi để đăng ký BOI vào buổi tối, nên cần trả lời câu hỏi này cho \(Q\) cặp sự kiện bắt đầu và kết thúc khác nhau.

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(N\) và \(Q\), lần lượt là số sự kiện và số cặp sự kiện cần tìm số lần chuyển ít nhất.

\(N\) dòng tiếp theo mô tả các sự kiện. Dòng thứ \(i\) chứa hai số nguyên \(S_i\) và \(E_i\), là thời điểm bắt đầu và kết thúc của sự kiện \(i\).

\(Q\) dòng tiếp theo mô tả các truy vấn. Dòng thứ \(i\) chứa hai số nguyên \(s_i\) và \(e_i\), yêu cầu tìm số lần chuyển sự kiện ít nhất để bắt đầu ở sự kiện \(s_i\) và kết thúc chuyến tham dự ở sự kiện \(e_i\).

Dữ liệu ra

In \(Q\) dòng. Dòng thứ \(i\) chứa số lần chuyển sự kiện ít nhất cho truy vấn thứ \(i\), hoặc chuỗi impossible nếu không có cách thực hiện.

Ràng buộc

• \(1\le N,Q\le100\,000\).
• \(1\le S_i<E_i\le10^9\) với \(1\le i\le N\).
• \(1\le s_i,e_i\le N\) với \(1\le i\le Q\).
• Giới hạn thời gian: \(1\) giây.
• Giới hạn bộ nhớ: \(512\) MiB.

Phân nhóm

1. \(10\) điểm: từ mỗi sự kiện, có thể chuyển sang nhiều nhất một sự kiện khác.
2. \(10\) điểm: \(N\le1\,000\) và \(Q\le100\).
3. \(15\) điểm: \(N\le5\,000\).
4. \(15\) điểm: \(Q\le100\).
5. \(20\) điểm: không có sự kiện nào nằm hoàn toàn trong một sự kiện khác; tức là không tồn tại hai sự kiện \(i\ne j\) sao cho \(S_i\le S_j<E_j\le E_i\).
6. \(30\) điểm: không có ràng buộc thêm.

Ví dụ

5 2
1 3
2 4
4 7
7 9
3 7
1 4
3 2

2
impossible

8 5
1 2
3 4
1 5
6 7
5 10
10 20
15 20
999999999 1000000000
1 6
1 7
2 4
3 3
5 8

3
4
impossible
0
impossible

Những sự kiện bạn tham dự vào ngày mới đến là cơ hội thú vị để làm quen lại với tình hình nghệ thuật đương đại. Hơn nữa, những lời đồn nghe được còn tiết lộ rằng bộ sưu tập bạn quan tâm được cất trong một kho bí mật dưới nước ở biển Baltic gần đó, thuộc sở hữu của một gia đình thương nhân ngũ cốc lâu đời tại Lübeck! Nhớ lại thời làm kẻ trộm tranh, bạn quyết định lên kế hoạch đột nhập kho như một hoạt động thư giãn buổi chiều. Dĩ nhiên, đây chỉ là một vụ trộm giả định.

Bạn muốn dùng chiếc tàu ngầm mới mua để đột nhập. Đáng tiếc là khi thoát khỏi hiện trường, tàu cần một tổng lực nâng chính xác bằng \(L\). Bạn đâu muốn tàu đâm xuống đáy biển hay nổi lên mặt nước để cảnh sát dễ dàng bắt được!

Để lên kế hoạch, bạn cần biết lực nâng của các tác phẩm nghệ thuật trong kho. Với kỹ năng của mình, bạn đã lấy được thông tin cần thiết — hệ thống an ninh của họ dùng thuật toán băm yếu thì đâu phải lỗi của bạn. Với mỗi giá trị lực nâng \(\ell\), bạn biết có bao nhiêu tác phẩm \(A_\ell\) mang lực nâng đó.

Hẳn có một câu chơi chữ về “phishing” ẩn ở đây, nhưng thú thật là chuyện này quá sâu so với chúng tôi.

Hãy viết chương trình dùng thông tin này để tính số tác phẩm nhiều nhất có thể lấy sao cho tổng lực nâng của chúng, bằng tổng lực nâng riêng của từng tác phẩm được lấy, đúng bằng \(L\), hoặc xác định rằng điều đó là không thể.

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(M\) và \(L\): lực nâng của mỗi tác phẩm nằm trong đoạn từ \(-M\) đến \(M\), kể cả hai đầu mút, và tổng lực nâng cần đạt là \(L\).

Dòng tiếp theo chứa \(2M+1\) số nguyên \(A_{-M},\ldots,A_M\), trong đó \(A_\ell\) là số tác phẩm có lực nâng \(\ell\) trong kho.

Dữ liệu ra

In một dòng chứa số tác phẩm nhiều nhất có thể lấy sao cho tổng lực nâng đúng bằng \(L\), hoặc chuỗi impossible nếu không có cách thực hiện.

Ràng buộc

• \(1\le M\le300\).
• \(-10^{18}\le L\le10^{18}\).
• \(0\le A_\ell\le10^{12}\) với mọi \(-M\le\ell\le M\).
• Giới hạn thời gian: \(4\) giây.
• Giới hạn bộ nhớ: \(512\) MiB.

Phân nhóm

1. \(5\) điểm: \(M\le50\) và \(A_\ell\le50\) với mọi \(-M\le\ell\le M\).
2. \(15\) điểm: \(M\le100\) và \(A_\ell\le100\) với mọi \(-M\le\ell\le M\).
3. \(20\) điểm: \(M\le30\). Nhận \(50\%\) số điểm của phân nhóm nếu giải đúng tất cả các bộ dữ liệu trong phân nhóm thỏa mãn \(A_\ell=0\) với mọi \(-M\le\ell<0\).
4. \(20\) điểm: \(M\le50\). Nhận \(50\%\) số điểm của phân nhóm nếu giải đúng tất cả các bộ dữ liệu trong phân nhóm thỏa mãn \(A_\ell=0\) với mọi \(-M\le\ell<0\).
5. \(20\) điểm: \(M\le100\). Nhận \(50\%\) số điểm của phân nhóm nếu giải đúng tất cả các bộ dữ liệu trong phân nhóm thỏa mãn \(A_\ell=0\) với mọi \(-M\le\ell<0\).
6. \(20\) điểm: không có ràng buộc thêm. Nhận \(50\%\) số điểm của phân nhóm nếu giải đúng tất cả các bộ dữ liệu trong phân nhóm thỏa mãn \(A_\ell=0\) với mọi \(-M\le\ell<0\).

Trong CMS chính thức, phần dữ liệu không có tác phẩm mang lực nâng âm nói trên được hiển thị là Group 1 của từng phân nhóm từ \(3\) đến \(6\).

Ví dụ

2 5
2 3 1 1 4

9

3 5
3 1 0 2 0 0 2

impossible

1 5
0 0 6

5