Huyền thoại Lục Vân Tiên

Points: 0.08 (partial)

Time limit: 1.0s

Memory limit: 512M

Input: stdin

Output: stdout

Problem types

Allowed languages

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

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~ ~\rightarrow~ ~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~ ~\rightarrow~ ~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, \dots, 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~ ~\rightarrow~ vị ~k~

Phương án ~2~: Vân Tiên phải đấu với vị ~2~ ~\rightarrow~ vị ~k+1~ ...

Phương án ~N-k+1~: Vân Tiên phải đấu với vị ~N-k+1~ ~\rightarrow~ vị ~N~).

~(1 \leq N \leq 17000~, chỉ số APM của 1 giám khảo ~\geq 1~ và ~\leq 2~ tỉ, ~1 \leq K \leq N)~.

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_2~, ...~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~.

Sample Input

Sample Output

2 2 1 
1

Comments

Please read the guidelines before commenting.

-5

Huy_inIT commented on July 27, 2024, 12:05 p.m.

include <iostream>

include <deque>

int numTest; int n, k; int a[17005];

int main () { std::cin >> numTest; for (int testCase = 1; testCase <= numTest; testCase++) { std::cin >> n >> k; for (int i = 1; i <= n; i++) { std::cin >> a[i]; } std::deque <int> dq; for (int i = 1; i <= k; i++) { while (!dq.empty() && a[i] < dq.back()) { dq.popback(); } dq.pushback(a[i]); } std::cout << dq.front() << ' '; for (int i = k + 1; i <= n; i++) { if (dq.front() == a[i - k]) { dq.popfront(); } while (!dq.empty() && a[i] < dq.back()) { dq.popback(); } dq.push_back(a[i]); std::cout << dq.front() << ' '; } std::cout << std::endl; } return 0; }

This comment is hidden due to too much negative feedback. Show it anyway.

-6

aqua_envi_striker commented on Feb. 1, 2024, 3:51 a.m.

LÒwÓng

This comment is hidden due to too much negative feedback. Show it anyway.

-4

khanh2212 commented on Jan. 21, 2024, 3:19 p.m.

LOWG

-12

hieubecclc01 commented on Oct. 6, 2022, 2:40 p.m. ← edit 3 →

[DELETE]

This comment is hidden due to too much negative feedback. Show it anyway.

-12

toidaidot2 commented on June 22, 2023, 8:59 a.m.

nhầm tí =))

This comment is hidden due to too much negative feedback. Show it anyway.

-10

toidaidot2 commented on June 22, 2023, 9:02 a.m.

à đúng rồi =))

This comment is hidden due to too much negative feedback. Show it anyway.

-13

hh123123 commented on Oct. 6, 2022, 4:20 p.m.

Ai hỏi thế

This comment is hidden due to too much negative feedback. Show it anyway.

-7

CBNK30_tungle commented on Oct. 12, 2022, 7:52 a.m.

me

This comment is hidden due to too much negative feedback. Show it anyway.

-7

CBNK30_DucNhat commented on Oct. 12, 2022, 7:58 a.m.

oke

This comment is hidden due to too much negative feedback. Show it anyway.

-7

htmanh commented on Oct. 12, 2022, 7:31 a.m.

i asked XD

This comment is hidden due to too much negative feedback. Show it anyway.

-13

CBNK30_hieu commented on Oct. 12, 2022, 7:41 a.m.

lm đi mạnh đần

This comment is hidden due to too much negative feedback. Show it anyway.

-7

iamqazolp commented on Oct. 7, 2022, 12:56 a.m.

toi hoi

This comment is hidden due to too much negative feedback. Show it anyway.

-25

ntkiet commented on May 1, 2022, 1:33 p.m.

ඞ

This comment is hidden due to too much negative feedback. Show it anyway.

-75

nngovannhhungg commented on Jan. 14, 2022, 6:56 a.m.

bài này quá dễ

This comment is hidden due to too much negative feedback. Show it anyway.

21

I_love_Hoang_Yen commented on April 9, 2021, 3:21 p.m.

Nên giảm time limit để thuật n*log không AC :D

21

leduykhongngu commented on April 10, 2021, 5:25 a.m.

Em nghĩ nên tăng giới hạn n, tại vì 17000 thì nlogn với n nó không khác nhau mấy :v