trang chủ / đề bài / icpcwf23_h

Lệch múi giờ

Đề bài

Mô tả

Vòng chung kết ICPC thế giới đã đến, với vô số hoạt động bạn muốn tham dự: các bài phát biểu, bài thuyết trình, sự kiện vui chơi, chưa kể chính cuộc thi. Chỉ có một vấn đề: khi nào bạn sẽ ngủ?

Mỗi khi đi ngủ, bạn luôn đặt hẹn giờ, vì nếu không bạn có thể ngủ mãi. Nhờ hẹn giờ, bạn có thể chọn ngủ trong một số phút nguyên dương bất kỳ. Sau khi ngủ k phút, bạn sẽ ở trạng thái tỉnh táo trong k phút tiếp theo (nên bạn không thể ngủ lại được); rồi bạn vẫn hoạt động được thêm k phút thứ ba (trong khoảng này bạn có thể tiếp tục thức, nhưng cũng có thể đi ngủ nếu muốn).

Bạn biết thời gian của mọi hoạt động trong vòng chung kết; hãy lập lịch ngủ sao cho không bỏ lỡ bất kỳ phần nào của bất kỳ hoạt động nào. Ngay trước khi vòng chung kết bắt đầu (tại phút 0), bạn về tới phòng khách sạn sau một chuyến đi dài và cần đi ngủ ngay lập tức.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên dương n (1≤n≤200000): số hoạt động được lên kế hoạch.

Dòng thứ i trong n dòng tiếp theo chứa hai số nguyên bi và ei: thời điểm bắt đầu và kết thúc của hoạt động thứ i, tính bằng phút kể từ lúc vòng chung kết bắt đầu. Biết bi<ei, ei≤bi+1, 0≤b1 và en≤1010.

Dữ liệu ra

Nếu tồn tại lịch ngủ cho phép bạn tham gia trọn vẹn mọi hoạt động đã lên kế hoạch, hãy in ra một lịch như vậy theo định dạng dưới đây. Ngược lại, in ra impossible.

Lịch ngủ gồm một dòng chứa số p (1≤p≤106) là số lần ngủ, tiếp theo là p dòng. Dòng thứ i trong số đó chứa hai số nguyên si và ti: thời điểm bắt đầu và kết thúc của lần ngủ thứ i, tính bằng phút kể từ lúc vòng chung kết bắt đầu. Không được in lần ngủ nào sau hoạt động cuối cùng.

Các lần ngủ phải thỏa mãn 0=s1<t1<s2<t2<…<tp≤bn, cùng với điều kiện đã mô tả ở trên là không được ngủ trong một khoảng thời gian sau mỗi lần ngủ. Bạn có thể đi ngủ ngay sau khi một hoạt động kết thúc (tức là có thể si=ej) và có thể thức dậy ngay trước khi một hoạt động bắt đầu (tức là có thể ti=bj).

Nếu có nhiều lịch ngủ hợp lệ, in ra lịch bất kỳ. Có thể chứng minh rằng nếu tồn tại lịch ngủ hợp lệ thì cũng tồn tại lịch có không quá 106 lần ngủ.

Ràng buộc

  • 1≤n≤200000.
  • 0≤b1, bi<ei≤bi+1, en≤1010; mọi giá trị là số nguyên.

Ví dụ

Input Output Giải thích
3
30 45
60 90
120 180
2
0 30
90 120
Ngủ 30 phút từ 0 đến 30: tỉnh táo tới phút 60 và hoạt động được tới phút 90, đủ cho hai hoạt động đầu. Sau đó ngủ 30 phút từ 90 đến 120, hoạt động được tới phút 180, đúng lúc hoạt động cuối kết thúc.
1
0 60
impossible Bạn phải ngủ ngay tại phút 0, nhưng hoạt động duy nhất cũng bắt đầu tại phút 0.
7
31 32
35 41
48 55
69 91
1000 2022
2022 2023
2994 4096
5
0 5
10 28
56 68
92 900
2025 2900
Chẳng hạn lần ngủ [10,28] dài 18 phút: không được ngủ trước phút 46, phải ngủ lại muộn nhất ở phút 64; lần ngủ tiếp theo bắt đầu ở phút 56. Lần ngủ cuối [2025,2900] giúp bạn hoạt động tới phút 4650≥4096.

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