oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

shouting Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

shouting.html

Problem Description

Peanut has recently taught his cats how to count from 1 to K. As such, he is very excited and wants to hear them count all at once!

However, cats are inherently very chaotic. Peanut gives his cats a total time period of N seconds to complete counting. Each cat starts counting from a certain integer number of seconds from the beginning of this time period, and shouts one number every second, until it reaches K, after which it stops counting.

As all the cats are shouting at the same time, it is difficult for Peanut to decipher the individual noises. In each second, Peanut can only hear the number that the most number of cats are shouting. If two different numbers are being shouted by the same number of cats, Peanut will only hear the smaller number.

Given a list of N numbers that Peanut can hear for each individual second, Peanut wants to know, for each second, how many cats started counting in that second. If there is more than one solution, output the one that minimises the total number of cats Peanut has, as Peanut is very very sure he doesn't have that many cats. If multiple solutions have the same number of cats, output any of them. It is guaranteed at least one valid solution exists.

Input

The first line of input will contain two integers, N and K.

The second line of input will contain N integers, with the ith integer representing the number Peanut hears in the ith second.

Output

The output should contain N integers, with the ith integer representing how many cats have started shouting at time i.

Limits

Any valid solution where the total number of cats does not exceed 1018 will be given 50% for the subtask.

For all subtasks: 2 ≤ K ≤ N ≤ 500 000.

Subtask 1 (14%): 2 ≤ K ≤ N ≤ 8.

Subtask 2 (15%): 2 ≤ K ≤ 50, 2 ≤ N ≤ 30 000.

Subtask 3 (17%): K = 2.

Subtask 4 (13%): K = N - 1.

Subtask 5 (10%): The optimal answer will have no more than 2 cats.

Subtask 6 (11%): An optimal solution exists such that no two cats start at the same time.

Subtask 7 (20%): No additional constraints.

Subtask 8 (0%): Sample Testcases.

Sample Input 1

5 3
1 2 1 2 3

Sample Output 1

1 0 1 0 0

Explanation for Sample 1

Peanut has two cats: one starting to shout at time 0, the other starting to shout at time 2. At time 2, 1 and 3 are being shouted by one cat each, so Peanut only hears 1. At all other times, there is only one cat shouting.

Sample Input 2

4 2
1 1 1 2

Sample Output 2

1 1 1 0

Sample Input 3

10 5
1 2 1 2 3 4 5 4 5 5

Sample Output 3

1 0 3 0 2 1 0 0 0 0

Tags

Ad Hoc, Greedy, Dynamic Programming

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
114221s256MBMinimum
215431s256MBMinimum
317211s256MBMinimum
413201s256MBMinimum
510211s256MBMinimum
611421s256MBMinimum
7201431s256MBMinimum
8031s256MBMinimum

Judge Compile Command

g++-8 ans.cpp -o shouting -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.