Lập lịch giảm thiểu trễ hạn

Xem dạng PDF

Gửi bài giải


Điểm: 0,35 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout

Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Có ~n~ công việc đánh số từ ~1~ đến ~n~ và một máy để thực hiện chúng. Biết:

  • ~p_{i}~ là thời gian cần thiết để hoàn thành công việc ~i~.
  • ~d_{i}~ là thời hạn hoàn thành công việc ~i~.

Máy bắt đầu hoạt động từ thời điểm ~0~. Mỗi công việc cần được thực hiện liên tục từ lúc bắt đầu cho tới khi kết thúc, không cho phép ngắt quãng. Giả sử ~c_{i}~ là thời điểm hoàn thành công việc ~i~. Khi đó, nếu ~c_{i} > d_{i}~ ta nói công việc ~i~ bị hoàn thành trễ hạn, còn nếu ~c_{i} \leq d_{i}~ thì ta nói công việc ~i~ được hoàn thành đúng hạn.

Yêu cầu: Tìm trình tự thực hiện các công việc sao cho số công việc hoàn thành trễ hạn là ít nhất.

Input

  • Dòng đầu tiên chứa số nguyên dương ~n~ (~0 < n \leq 100000~).
  • Dòng thứ hai chứa ~n~ số nguyên dương ~p_{1}~, ~p_{2}~, ..., ~p_{n}~ (~0 < p_{i} \leq 10000~).
  • Dòng thứ ba chứa ~n~ số nguyên dương ~d_{1}~, ~d_{2}~, ..., ~d_{n}~ (~0 < d_{i} \leq 10000~).

Output

  • Dòng đầu tiên ghi số lượng công việc bị hoàn thành trễ hạn theo trình tự tìm được.
  • Dòng tiếp theo ghi ~n~ số nguyên dương là chỉ số của các công việc theo trình tự thực hiện tìm được.

Sample Input

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

Sample Output

2
1 3 4 6 2 5

Note

  • Có 50% số test có ~n \leq 100~.

Bình luận

Hãy đọc nội quy trước khi bình luận.


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