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

fishsort Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

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

fishsort.html

Problem Description

Rar the Cat is bored and has nothing much to do. To entertain himself, he intends to sort some heaps of fishes!

Rar the Cat wants to sort N heaps of fishes today. Each heap must have at least 1 fish, but not more than 109 fishes. (P.S. these fishes can be extremely small).

For today, Rar the Cat has exactly K seconds of free time that he intends to entertain himself through fish-sorting. If he spends less than K seconds sorting the fishes, he would be bored for the remaining amount of time and be unhappy. On the other hand, if he spends more than K seconds sorting the fishes, he would be late for his next activity and will also be unhappy. Hence, it is of utmost importance that the fish-sorting activity takes exactly K seconds.

Luckily, Rar the Cat is very predictable. In his fish sorting, he always uses a bubble sort algorithm and swapping two adjacent heaps takes exactly 1 second for Rar the Cat. In addition, since Rar the Cat is greedy, he will prefer that larger heaps of fish appear first in the final sorted sequence.

For example, if Rar the Cat is sorting through N = 5 heaps of fishes today with the initial sequence S = {2, 5, 3, 7, 1}, the final sequence will be {7, 5, 3, 2, 1} and this will take him exactly 5 seconds as it would require 5 swaps.

Your task, is to find a initial sequence S, representing heaps of fishes for Rar the Cat to perform bubble sort. S should have exactly N elements and takes K swaps to sort in descending order.

As a reference, below is a pseudo-code of Rar's bubble sort algorithm

for (int i = 0; i < N; i++) {
    for (int j = 0; j < N-1; j++) {
        if (heap j is less than heap j+1) {
            swap position of heap j and heap j+1
        }
    }
}

Limits

For all tests: 0 ≤ K ≤ N * (N-1) / 2.

Subtask 1 (8%): 1 ≤ N ≤ 3

Subtask 2 (12%): 1 ≤ N ≤ 300.

Subtask 3 (37%): 1 ≤ N ≤ 3000.

Subtask 4 (4%): 1 ≤ N ≤ 1000000, K = 0.

Subtask 5 (5%): 1 ≤ N ≤ 1000000, 0 ≤ K < N.

Subtask 6 (34%): 1 ≤ N ≤ 1000000.

Subtask 7 (0%): Sample Testcases.

Input

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

Output

You are to output the initial sequence S which contains N integers from 1 to 109, space separated.

Multiple answers are accepted as long as they require exactly K swaps for Rar the Cat to sort them in descending order.

Sample Testcase 1

Input

5 5

Output

2 5 3 7 1

Sample Testcase 2

Input

5 5

Output

1 3 1 3 3

Sample Testcase 3

Input

5 10

Output

1 2 3 4 5

Tags

Sorting

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
1871s64MBMinimum
212241s64MBMinimum
337381s64MBMinimum
4451s64MBMinimum
55251s64MBMinimum
634801s64MBMinimum
7031s64MBMinimum

Judge Compile Command

g++-8 ans.cpp -o fishsort -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.