trang chủ / đề bài / icpcwf24_d

Vật trên lưng ngựa đôi

Đề bài

Mô tả

Ủy ban Thăm dò Đại hội Thể thao Du mục (NGEC) đang thăm dò ý tưởng tổ chức một giải đấu vật trên lưng ngựa đôi, trong đó mỗi đội gồm hai kỵ sĩ cùng cưỡi một con ngựa. Ủy ban đã quảng bá một giải đấu thử nghiệm, và đã có n kỵ sĩ hăng hái đăng ký thi đấu! Giờ NGEC cần ghép các kỵ sĩ thành từng cặp sao cho giải đấu vừa công bằng vừa hấp dẫn.

Liên đoàn Audaryspak Trung Á (CAAL) lưu danh sách tất cả các đô vật trên lưng ngựa cùng điểm xếp hạng của họ. Từ kinh nghiệm với môn vật trên lưng ngựa thông thường, NGEC quyết định rằng một cặp cân bằng nhất khi tổng điểm xếp hạng của hai kỵ sĩ bằng đúng một số nguyên s cho trước.

Vì những lý do bản quyền khó hiểu, CAAL từ chối công bố điểm xếp hạng chính xác của từng kỵ sĩ. Tuy vậy, NGEC có những ước lượng khá tốt: họ biết điểm xếp hạng thật ri của kỵ sĩ i nằm trong đoạn [li,ui]. Vì vậy NGEC sẽ cân nhắc ghép hai kỵ sĩ i và j thành một cặp nếu tồn tại các điểm xếp hạng ri∈[li,ui] và rj∈[lj,uj] sao cho ri+rj=s.

NGEC muốn tạo ra nhiều cặp kỵ sĩ nhất có thể, trong đó không có kỵ sĩ nào thuộc hai cặp. Hãy giúp họ.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên n và s (2≤n≤2·105, 1≤s≤109): số kỵ sĩ và tổng điểm xếp hạng mong muốn của hai kỵ sĩ trong một cặp. Các kỵ sĩ được đánh số từ 1 đến n.

Tiếp theo là n dòng, dòng thứ i chứa hai số nguyên li và ui (1≤li≤ui≤109): đoạn điểm xếp hạng của kỵ sĩ thứ i.

Dữ liệu ra

In ra k, số cặp lớn nhất có thể tạo được, sau đó là k dòng, mỗi dòng gồm hai số nguyên là số hiệu của hai kỵ sĩ trong một cặp. Nếu có nhiều cách ghép cặp, in ra cách bất kỳ.

Ràng buộc

  • 2≤n≤2·105, 1≤s≤109.
  • 1≤li≤ui≤109.

Ví dụ

Input Output Giải thích
6 10
6 7
1 4
2 2
3 8
5 7
9 9
2
6 2
3 4
Kỵ sĩ 6 (r=9) ghép với kỵ sĩ 2 (r=1), kỵ sĩ 3 (r=2) ghép với kỵ sĩ 4 (r=8). Không có hai kỵ sĩ nào trong nhóm 1, 3, 5, 6 ghép được với nhau, nên mỗi cặp phải chứa kỵ sĩ 2 hoặc kỵ sĩ 4: không thể có 3 cặp.
4 10
5 5
4 6
1 2
3 3
1
1 2
Kỵ sĩ 3 cần bạn có điểm từ 8 đến 9, kỵ sĩ 4 cần bạn có điểm 7: không ai đáp ứng được. Chỉ ghép được kỵ sĩ 1 với kỵ sĩ 2 (5+5=10).

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0