LCC '23 Contest 1 S1 - Weakest Warriors

View as PDF

Submit solution


Points: 5 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

This year, upon arriving home from Trick-or-Treating, JojoTheWarrior is exhausted after pretending to be a kid and looting his entire neighborhood for several hours. As a reward, though, he received a huge amount of candy this year, which he plans on having some fun with.

Slamming his massive haul of Halloween candy on the table and shrieking with excitement, JojoTheWarrior hastily unwraps his candies and sets them up in a row. He has N candies in total and the ith candy has a fighting value of A_i.

You might be wondering what he's about to do with those candies and why the candies have fighting values - don't worry, your questions will be answered shortly. JojoTheWarrior likes to assign random objects with fighting values in preparation of making them battle in tournaments. This is his way of entertaining himself when he's bored.

He can't remember when this habit of his started. It was probably around when he was in the third grade, when he was sitting in his boring class one day and barely paying attention to his yapping teacher. Many great things were born from boredom, as when the mind wanders, it can come up with some pretty sensational ideas.

The year was 2015 (probably). It was a chilly autumn day in late October, and the leaves were turning orange and golden. Lunch break had just ended a few minutes ago, and a young JojoTheWarrior was daydreaming in class, his thoughts still lingering on the enjoyable moments from just a few minutes earlier.

JojoTheWarrior always spent his lunchtimes with his friends. They would exchange snacks and lunch items for the first half of lunch, bargaining through a complex barter system. Then, having eaten, they would organize some type of schoolyard game, such as Manhunt or Tag, and spend the rest of lunch prancing around the field with each other and laughing. Looking back at those days of youthfulness always evokes a sense of nostalgia in JojoTheWarrior as he misses his old friends.

Despite its brevity, the lunchtime was cherished and enjoyed to the fullest. It was not just a time to refuel the body but also a chance to nourish the soul through spending quality time with friends, appreciating the refreshing air of nature and exercising. It's the type of moment that feels rather insignificant in the moment, but can only be truly appreciated through the rear-view mirror. That day, his friends brought a variety of Halloween candies to school and they were sharing them amongst themselves. JojoTheWarrior also brought a basketball that day, so they played a game of HORSE in the courtyard after snacking on the Halloween sweets.

Suddenly, the shrill bell rang, marking the end of his favourite part of his day. Moments later, JojoTheWarrior found himself locked in a classroom, sitting on the opposite side of the room from his friends.

His teacher was yapping on about some English assignment that was due the next day - the assignment was something along the lines of writing a poem about your favourite animal. JojoTheWarrior loved rabbits and would gladly verbally talk about them, but he hated the idea of writing a cringey poem about them. He had not even started on the poem yet, and felt stressed out. His creative writing skills are still one of his weaknesses, and he often thinks back to this poem assignment whenever he has to do creative writing in school - even now, almost 8 years later!

JojoTheWarrior suddenly noticed that the teacher stopped talking and realized that she probably asked them a question. He could not figure out what the question was, let alone answer it, so he remained quiet. In fact, JojoTheWarrior rarely ever talked in class in elementary school. Looking back, this is probably also where his habits of not participating in class began. It's wild how influential one's childhood can be to one's personality traits, isnt' it?!

Thankfully, just when the quiet room was getting awkward, one of his classmates (the teacher's pet) answered with a lengthy response. The young, chatty student kept talking, and eventually JojoTheWarrior tuned him out.

JojoTheWarrior sighed and checked the clock, hoping that this class would end sooner. Unfortunately, not even five minutes had passed since lunch ended - JojoTheWarrior had at least an hour more to hold out! He promised himself that he wouldn't check the clock again for at least ten more minutes.

Oh, how terrible a fate to suffer! The young JojoTheWarrior felt imprisoned in this classroom.

He distractedly gazed around, searching for something to search for. Pumpkins hung from the celings. The teacher's whiteboard had an orange and black style, with stapled cartoon posters that the teacher bought from Dollarama. There were paper cutouts of spooky skeletons dancing on the wall, too, reminding JojoTheWarrior of a trendy meme back at that time. JojoTheWarrior couldn't help but scoff at his teacher's distasteful choice of decor.

Yawning, JojoTheWarrior, about halfway dead from boredom, picked up a pencil in his right hand, fidgeting with it and spinning it back and forth. The pencil fit snugly between his short fingers, and he mindlessly twirled it. He picked up another pencil in his left hand and held it in the same manner between his thumb and index finger, supported on his middle finger's phalanx.

Then, suddenly, his tired eyes open wide. A visiting thought passed through his mind, stopping for just long enough for him to catch it. The revoluntionary idea became clear.

Both of his hands suddenly transformed into skilled swordsmen, one wielding an epic ninja katana forged from the iron of some cool Japanese mountain and the other a magical Excalibur with monstrous power. The swordsmen charged at each other, swinging their deadly slashes and deflecting their opponent's blows. Clashing their blades together, both swordsmen pushed forward with all their might, struggling to overpower the other. Eventually, they released from the bind, taking a few steps back to recover - it seemed like they were of the same caliber. JojoTheWarrior kept the swordfight going for ten minutes, then found new types of swords from his backpack to further entertain himself.

Different types of swords had different abilities - for example, some had poison damage, others could shoot freezing blasts, and the ones with a hook could disarm their opponents. Tournament brackets were set up to determine who the strongest swordsman was. The swordsmen would be ranked by their fighting value, a positive integer less than ten (JojoTheWarrior did not know too many numbers back then). Then, the swordsmen would be sorted in increasing order. To keep things fair for the weaker swordsmen, those with the lowest fighting values (more specifically, a prefix of the lowest swordsmen when ranked), known as the "Weakest Warriors", would form a tournament of their own, separate from the stronger swordsmen. Swords could be upgraded by adding attachments and accessories. Each swordsman could wield a sidearm, too, such as a coiled iron kunai (a paperclip) or a resilient wooden longshield (a popsicle stick). JojoTheWarrior kept playing for so long that before he even knew it, the bell rang, finally releasing him from the prison. Ironically, though, he was actually hoping that the period would last a little longer; his tournament was only halfway finished.

Now, let's go back to the present day. It seems JojoTheWarrior's habit of playing with random objects - with absolutely anything and everything - persisted from his childhood. JojoTheWarrior (he can barely contain himself) jumps up and down, clapping his little piggy hands together and giggling. He cannot wait to begin the candy warrior battles!

Constraints

1 \le A_i \le 11

Subtask 1 [70%]

1 \le K \le N \le 10

Subtask 2 [30%]

1 \le K \le N \le 10^3

Input Specification

The first line contains the integer N and K.

The second line contains N space separated integers, the ith (1 \le i \le N) one representing A_i, the fighting value of the ith candy.

Output Specification

Print the indices of the K weakest candies, space-separated. If two candies have the same fighting value, the one with a lower index is stronger. The indices should be printed in increasing order.

Sample Input 1

9 7
11 11 7 11 1 2 1 7 2

Sample Output 1

3 4 5 6 7 8 9

Sample Explanation 1

The 2 strongest candies are the only ones that are not printed, since 9 - 7 = 2.

Out of indices 1, 2 and 4, which are all tied with a fighting value of 11, candy #4 has the highest index which makes him the weakest amongst the three, and the seventh weakest overall.


Comments

There are no comments at the moment.