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

platforms Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

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

platforms.html

Problem Description

There are N platforms in front of Jie Feng numbered 1 to N. Platform i is at height i metres from the ground.

Jie Feng wants to visit each platform exactly once. To do so, Jie Feng needs to make (N - 1) jumps between the platforms.

As it is dangerous for Jie Feng to make jumps where the difference in height is large, he has a jetpack to help him.

Before making any jump, in order to operate the jetpack, Jie Feng has to first input K distinct integers into the jetpack: the jump heights that the jetpack is allowed to operate on.

Jie Feng can only jump between two platforms if the absolute difference in their heights is one of the K integers Jie Feng has entered in the jetpack.

Moreover, to avoid damaging the jets in his jetpack, Jie Feng has to ensure that he utilizes every jump height at least once. This means that each of the K jump heights must be equal to the height difference between two platforms of at least one of the (N - 1) jumps Jie Feng makes.

Help Jie Feng to find any valid order to visit the platforms, and the K jump heights Jie Feng inputs for the order that you have found. It is guaranteed that there is at least one valid way to visit the platforms.

Input

The only line of input contains two integers, N, the number of platforms, and K, the number of jumps heights Jie Feng needs to input.

Output

On the first line, output K integers, the jump heights that Jie Feng needs to input into the jetpack.

On the following line, output N integers. The ith integer should indicate the ith platform that Jie Feng should visit.

Limits

Subtask 1 (12%): 2 ≤ N ≤ 1 000 000. K = 1.

Subtask 1 (14%): 3 ≤ N ≤ 1 000 000. K = 2.

Subtask 3 (14%): 1 ≤ K < N ≤ 4.

Subtask 4 (19%): 1 ≤ K < N ≤ 11.

Subtask 5 (41%): 1 ≤ K < N ≤ 1 000 000.

Subtask 6 (0%): Sample Testcases

Sample Testcase 1

Input

6 2

Output

2 5
2 4 6 1 3 5

Tags

Ad Hoc

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
11260.5s256MBMinimum
214140.5s256MBMinimum
31460.5s256MBMinimum
419500.5s256MBMinimum
541700.5s256MBMinimum
6010.5s256MBMinimum

Judge Compile Command

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