CAPTAIN M & ARMY
All submissions for this problem are available.
Secret sources of an army has given some information about locations of terrorist camps and how many terrorists are present there.Army has decided to kill those terrorists before they plan anything wrong.This mission is assigned to Captain M (Leader) with a team of N soldiers.Each soldier has a long range sniper rifle with maximum Ni firing shots available initially.According to the sources there are K number of terrorists present.Capt.M want to kill all K terrorists and accordingly plan the strategies.
Capt.M has decided that only one soldier can fire only one shot at a time. soldier with maximum number of shots left will fire first.Then next soldier with higher number of shots left will fire and so on.In case if two or more soldiers are left with same number of shots then Capt.M will prefer the soldier in order of occurrence.Soldiers are not allowed to fire once their number of shots left is 0.
So as the leader of team,Capt M wants to decide the order of soldiers for killing terrorists. it is guaranteed that each single shot fired by soldier will kill exactly one terrorist.
Since the input might be large,use fast I/O techniques.
- The first line contains two integers N and K, which denote the number of soldiers and the total number of terrorists.
- The next line contains N space separated integers denoting the initial number of shots available for each soldiers.
- Print K space separated integers denoting the order of the soldiers chosen by Capt.M. The soldiers are 1-indexed.
- 1 ≤ N ≤ 1000000
- 1 ≤ K ≤ minimum (Σ Ni ,1000000)
- 1 ≤ Ni ≤ 1000000000
Input: 3 6 4 6 4 Output: 2 2 1 2 3 1
Initially,1st soldier has 4 shots,2nd has 6 shorts,3rd has 4 shots. soldier 2nd has higher number of shots left,so he will fire first then he is left with the 5 shots. again 2nd soldier has higher shots left among all so he will again fire one shot and so on.
|Tags||cfea2018, easy-medium, heaps, mehul_dholiya|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS|
Fetching successful submissions