Bedao Regular Contest 10 - BATTLESHIP

View as PDF

Submit solution


Points: 0.30 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

~Naot~ rất thích chơi bắn tàu. ~lành~ cũng thích chơi bắn tàu. Hai người rất thích bắn tàu với nhau và nghiễm nhiên trở thành "kỳ phùng địch thủ" của nhau. Bạn là trợ thủ đắc lực thiết kế tàu cho ~Naot~, hãy giúp anh ấy tạo nên một chiếc chiến hạm nhé!

Trong tựa game mô phỏng bắn tàu anh đang chơi, người chơi phải thiết kế con tàu bằng một dãy số nguyên dương có độ dài ~n~. Là một người đam mê dãy đối xứng, ~Naot~ quyết định thiết kế một "chiến hạm" với các đặc tính sau:

  • Vì muốn thiết kế một con tàu "ngon ngọt", ~Naot~ sẽ không quan tâm đến cấu hình đầu tiên của con tàu để cho "chiến hạm" của mình trông ngây thơ nhất có thể.

  • ~Naot~ là một người chơi bắn tàu lão làng thấu hiểu đối thủ, anh có thể đoán trước được ~lành~ có thể sẽ nhắm vào ~m~ vị trí trên con tàu, với thông tin này ~Naot~ muốn rằng ở lần đầu tiên con tàu mình bị bắn vào bất cứ vị trí nào trong ~m~ vị trí anh đoán trước thì dãy biểu diễn con tàu sẽ ghép ~n-1~ vị trí còn lại (giữ nguyên vị trí tương đối) sao cho thành một dãy đối xứng. Nói cách khác, với mỗi vị trí dự đoán, loại bỏ vị trí đó ra khỏi dãy và nhận được một dãy đối xứng độ dài ~n-1~.

  • Trò chơi đương nhiên sẽ cung cấp ~n~ loại nguyên liệu thiết kế tàu, các nguyên liệu được thể hiện dưới dạng các số nguyên dương không quá ~n~. ~Naot~ quan niệm rằng càng nhiều nguyên liệu lắp tàu thì "chiến hạm" của mình càng mạnh, anh quyết định chọn cách thiết kế tàu sử dụng nhiều loại nguyên liệu nhất. Nói cách khác số lượng giá trị phân biệt trong dãy là lớn nhất.

Dãy đối xứng là dãy khi viết ngược lại vẫn bằng dãy ban đầu.

Input

Dòng đầu tiên gồm hai số nguyên dương ~n~ và ~m~ (~1 \le m \le n \le 10^6~).

Dòng thứ hai chứa ~m~ số nguyên dương đôi một phân biệt không quá ~n~ là các vị trí trên con tàu có nguy cơ bị bắn cao nhất.

Output

Gồm một dòng duy nhất chứa ~n~ số nguyên dương không quá ~n~ là cấu hình "chiến hạm" thỏa mãn các đặc tính mà ~Naot~ mong muốn. Nếu có nhiều đáp án thỏa mãn, hãy in ra một cấu hình bất kỳ.

Subtask

  • ~60\%~ số test có ~1 \le m \le n \le 10^4~.

  • ~40\%~ số test còn lại không có điều kiện gì thêm.

Sample Input 1

6 2
2 4

Sample Output 1

1 2 2 3 2 1

Notes

Ở test ví dụ, chúng ta có ~2~ vị trí có nguy cơ bị bắn cao và khi loại bỏ ~2~ vị trí ấy ta lần lượt được ~2~ dãy:

  • Với vị trí ~2~ ta được: ~[1, 2, 3, 2, 1]~

  • Với vị trí ~4~ ta được: ~[1, 2, 2, 2, 1]~

Cả hai dãy nhận được đều là dãy đối xứng, vì vậy cấu hình trên thỏa mãn hai yêu cầu đầu tiên của ~Naot~ và cũng thỏa mãn yêu cầu cuối cùng với nhiều nguyên liệu nhất.


Comments

Please read the guidelines before commenting.



  • -6
    aRandomGuy   commented on Sept. 26, 2022, 2:39 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.