MINK - Huyền thoại Lục Vân Tiên
Giới hạn- Thời gian: 0.87s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Dạo này tivi cũng đang chiếu phim Lục Vân Tiên , sẵn tiện lấy luôn làm tiêu đề .
Lục Vân Tiên cũng giống Samurai Jack , bị Quan Thái Sư đẩy vào vòng xoáy thời gian và bị chuyển tới tương lai của những năm 2777 .
Ở thời đại này , Tráng sỹ phải là người thông thạo máy tính , gõ bàn phím lia lịa như đấu sỹ thời xưa múa kiếm ấy và phải qua một cuộc thi lập trình mới được phong danh hiệu .
Để vượt qua vòng loại , Vân Tiên cần tham gia cuộc thi sát hạch . Ban Giám Khảo cuộc thi sát hạch gồm có N người , họ đều là các cao thủ trong giới IT . Các thành viên trong Ban Giám Khảo được đánh số từ 1 -> N và mỗi người lại có một chỉ số sức mạnh gọi là APM ( Actions Per Minute ) . Các giám khảo sẽ xếp hàng lần lượt từ 1 -> N . Mỗi thí sinh sẽ phải đấu với K vị giám khảo và K vị giám khảo này phải đứng liền thành 1 đoạn ( Tức là i , i+1 , i+2 , ... i+K-1 ) , chỉ cần thắng 1 vị giám khảo thì sẽ vượt qua vòng loại .
Tuy nhiên thí sinh kô được chọn xem những giám khảo nào sẽ đấu với mình .
Vân Tiên rất lo vì lỡ may đụng độ với những vị giám khảo nào "khó nhằn" thì sẽ tiêu mất . Nên chiến thuật của Vân Tiên là tập trung hạ vị giám khảo có chỉ số APM thấp nhất trong số K vị . Bạn hãy lập trình để giúp Lục Vân Tiên xác định được ở tất cả các phương án thì chỉ số APM của vị giám khảo thấp nhất sẽ là bao nhiêu ( Có tất cả N-k+1 phương án :
Phương án 1 : Vân Tiên phải đấu với vị 1 -> vị k
Phương án 2 : Vân Tiên phải đấu với vị 2 -> vị k+1
…
Phương án N-k+1 : Vân Tiên phải đấu với vị N-k+1 -> vị N ) .
( 1 <= N <= 17000 , chỉ số APM của 1 giám khảo >= 1 và <= 2 tỉ , 1 <= K <= N ) .
Bài này O(N) mới thực sự coi là accept . Còn lại O(NlogN) hay O(N*K) thì bạn chỉ may mắn accept thôi .
Input
Dòng 1 : số T là số test .
Tiếp theo là T bộ test , mỗi bộ test có format như sau :
Dòng 1 : N k
Dòng 2 : N số nguyên dương A[1] , … A[N] .
Output
Kết quả mỗi test ghi ra trên dòng , dòng thứ i gồm N-k+1 số , số thứ j tương ứng là chỉ số APM của vị giám khảo yếu nhất trong phương án j .
Example
Input: 2 4 2 3 2 4 1 3 3 1 2 3 Output: 2 2 1 1
- Người up: hard7771988