시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB282594527.439%

문제

1부터 n까지의 정수가 단 한 번씩만 등장하는 크기가 n인 수열 x1, x2, ..., xn이 주어진다.

두 수를 바꾸는 "스왑"이라는 연산을 통해 수열을 수정할 수 있다. k=2, 3, ..., n 순서대로 k를 증가시키면서 xk와 x⌊k/2⌋를 바꿀지 말지 선택할 수 있다.

수열 a1, a2, ..., an이 수열 b1, b2, ..., bn보다 사전순으로 앞선다는 것은 k < j인  k에 대해 ak = bk를 만족하고 aj < bj를 만족하는 j (1 ≤ j ≤ n)가 존재한다는 것을 의미한다.

순서대로 "스왑" 연산을 하여 만들 수 있는 수열 중 가장 사전순으로 앞선 수열은 어떤 것일까?

입력

입력의 첫 줄에 정수 n이 주어진다.

둘째 줄에는 수열을 나타내는 n개의 정수가 공백으로 구분되어 주어진다.

출력

첫 줄에 순서대로 "스왑" 연산을 하여 만들 수 있는 수열 중 가장 사전순으로 앞선 수열을 나타내는 n개의 정수를 공백으로 구분하여 출력한다.

서브태스크 1 (10점)

  • 1 ≤ n ≤ 20

서브태스크 2 (11점)

  • 1 ≤ n ≤ 40

서브태스크 3 (27점)

  • 1 ≤ n ≤ 1000

서브태스크 4 (20점)

  • 1 ≤ n ≤ 5 ⋅ 104

서브태스크 5 (32점)

  • 1 ≤ n ≤ 2 ⋅ 105

예제 입력 1

5
3 4 2 5 1

예제 출력 1

2 1 3 4 5
W3sicHJvYmxlbV9pZCI6IjEyNzU0IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMmE0XHVjNjUxIiwiZGVzY3JpcHRpb24iOiI8cD4xXHViZDgwXHVkMTMwIG5cdWFlNGNcdWM5YzBcdWM3NTggXHVjODE1XHVjMjE4XHVhYzAwIFx1YjJlOCBcdWQ1NWMgXHViYzg4XHVjNTI5XHViOWNjIFx1YjRmMVx1YzdhNVx1ZDU1OFx1YjI5NCBcdWQwNmNcdWFlMzBcdWFjMDAgblx1Yzc3OCBcdWMyMThcdWM1ZjQgeDxzdWI+MTxcL3N1Yj4sIHg8c3ViPjI8XC9zdWI+LCAuLi4sIHg8c3ViPm48XC9zdWI+XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YzIxOFx1Yjk3YyBcdWJjMTRcdWFmYjhcdWIyOTQgJnF1b3Q7XHVjMmE0XHVjNjUxJnF1b3Q7XHVjNzc0XHViNzdjXHViMjk0IFx1YzVmMFx1YzBiMFx1Yzc0NCBcdWQxYjVcdWQ1NzQgXHVjMjE4XHVjNWY0XHVjNzQ0IFx1YzIxOFx1YzgxNVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBrPTIsIDMsIC4uLiwgbiBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMga1x1Yjk3YyBcdWM5OWRcdWFjMDBcdWMyZGNcdWQwYTRcdWJhNzRcdWMxMWMgeDxzdWI+azxcL3N1Yj5cdWM2NDAmbmJzcDt4PHN1Yj4mbGZsb29yO2tcLzImcmZsb29yOzxcL3N1Yj5cdWI5N2MgXHViYzE0XHVhZmMwXHVjOWMwIFx1YjlkMFx1YzljMCBcdWMxMjBcdWQwZGRcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMjE4XHVjNWY0IGE8c3ViPjE8XC9zdWI+LCBhPHN1Yj4yPFwvc3ViPiwgLi4uLCBhPHN1Yj5uPFwvc3ViPlx1Yzc3NCBcdWMyMThcdWM1ZjQgYjxzdWI+MTxcL3N1Yj4sIGI8c3ViPjI8XC9zdWI+LCAuLi4sIGI8c3ViPm48XC9zdWI+XHViY2Y0XHViMmU0IFx1YzBhY1x1YzgwNFx1YzIxY1x1YzczY1x1Yjg1YyBcdWM1NWVcdWMxMjBcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzQwIGsgJmx0OyBqXHVjNzc4ICZuYnNwO2tcdWM1ZDAgXHViMzAwXHVkNTc0IGE8c3ViPms8XC9zdWI+ID0gYjxzdWI+azxcL3N1Yj5cdWI5N2MgXHViOWNjXHVjODcxXHVkNTU4XHVhY2UwIGE8c3ViPmo8XC9zdWI+ICZsdDsgYjxzdWI+ajxcL3N1Yj5cdWI5N2MgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IGogKDEgJmxlOyBqICZsZTsgbilcdWFjMDAgXHVjODc0XHVjN2FjXHVkNTVjXHViMmU0XHViMjk0IFx1YWM4M1x1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyAmcXVvdDtcdWMyYTRcdWM2NTEmcXVvdDsgXHVjNWYwXHVjMGIwXHVjNzQ0IFx1ZDU1OFx1YzVlYyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWMyMThcdWM1ZjQgXHVjOTExIFx1YWMwMFx1YzdhNSBcdWMwYWNcdWM4MDRcdWMyMWNcdWM3M2NcdWI4NWMgXHVjNTVlXHVjMTIwIFx1YzIxOFx1YzVmNFx1Yzc0MCBcdWM1YjRcdWI1YTQgXHVhYzgzXHVjNzdjXHVhZTRjPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1Y2NhYiBcdWM5MDRcdWM1ZDAgXHVjODE1XHVjMjE4IG5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzIxOFx1YzVmNFx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgblx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMThcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgJnF1b3Q7XHVjMmE0XHVjNjUxJnF1b3Q7IFx1YzVmMFx1YzBiMFx1Yzc0NCBcdWQ1NThcdWM1ZWMgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjMjE4XHVjNWY0IFx1YzkxMSBcdWFjMDBcdWM3YTUgXHVjMGFjXHVjODA0XHVjMjFjXHVjNzNjXHViODVjIFx1YzU1ZVx1YzEyMCBcdWMyMThcdWM1ZjRcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IG5cdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4XHViOTdjIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWQ1NThcdWM1ZWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiIsInN1YnRhc2sxIjoiPHVsPlxyXG5cdDxsaT4xICZsZTsgbiAmbGU7IDIwPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzdWJ0YXNrMiI6Ijx1bD5cclxuXHQ8bGk+MSAmbGU7IG4gJmxlOyA0MDxcL2xpPlxyXG48XC91bD5cclxuIiwic3VidGFzazMiOiI8dWw+XHJcblx0PGxpPjEgJmxlOyBuICZsZTsgMTAwMDxcL2xpPlxyXG48XC91bD5cclxuIiwic3VidGFzazQiOiI8dWw+XHJcblx0PGxpPjEgJmxlOyBuICZsZTsgNSAmc2RvdDsgMTA8c3VwPjQ8XC9zdXA+PFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzdWJ0YXNrNSI6Ijx1bD5cclxuXHQ8bGk+MSAmbGU7IG4gJmxlOyAyICZzZG90OyAxMDxzdXA+NTxcL3N1cD48XC9saT5cclxuPFwvdWw+XHJcbiJ9LHsicHJvYmxlbV9pZCI6IjEyNzU0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU3dhcCIsImRlc2NyaXB0aW9uIjoiPHA+WW91IGFyZSBnaXZlbiBhIHNlcXVlbmNlIG9mIG4gbnVtYmVycyB4PHN1Yj4xPFwvc3ViPiwgeDxzdWI+MjxcL3N1Yj4sIC4uLiwgeDxzdWI+bjxcL3N1Yj4uIEVhY2ggbnVtYmVyIDEsIDIsIC4uLiwgbiBhcHBlYXJzIGV4YWN0bHkgb25jZSBpbiB0aGUgc2VxdWVuY2UuPFwvcD5cclxuXHJcbjxwPllvdSBjYW4gbW9kaWZ5IHRoZSBzZXF1ZW5jZSB1c2luZyBzd2Fwcy4gVGhlcmUgYXJlIG4gLSAxIGNvbnNlY3V0aXZlIHR1cm5zIG51bWJlcmVkIGsgPSAyLCAzLCAuLi4sIG4uIE9uIHR1cm4gayB5b3UgY2FuIGVpdGhlciBzd2FwJm5ic3A7dmFsdWVzIHg8c3ViPms8XC9zdWI+IGFuZCB4PHN1Yj4mbGZsb29yO2tcLzImcmZsb29yOyZuYnNwOzxcL3N1Yj5pbiB0aGUgc2VxdWVuY2Ugb3IgZG8gbm90aGluZy48XC9wPlxyXG5cclxuPHA+U2VxdWVuY2UgYTxzdWI+MTxcL3N1Yj4sIGE8c3ViPjI8XC9zdWI+LCAuLi4sIGE8c3ViPm48XC9zdWI+IGlzIGxleGljb2dyYXBoaWNhbGx5IHNtYWxsZXIgdGhhbiBzZXF1ZW5jZSBiPHN1Yj4xPFwvc3ViPiwgYjxzdWI+MjxcL3N1Yj4sIC4uLiwgYjxzdWI+bjxcL3N1Yj4gaWYgdGhlcmUgZXhpc3RzIGFuIGluZGV4IGogKDEgJmxlOyBqICZsZTsgbikgc3VjaCB0aGF0IGE8c3ViPms8XC9zdWI+ID0gYjxzdWI+azxcL3N1Yj4gZm9yIGFsbCBrICZsdDsgaiBhbmQgYTxzdWI+ajxcL3N1Yj4gJmx0OyBiPHN1Yj5qPFwvc3ViPi48XC9wPlxyXG5cclxuPHA+V2hhdCBpcyB0aGUgbGV4aWNvZ3JhcGhpY2FsbHkgbWluaW1hbCBzZXF1ZW5jZSB5b3UgY2FuIG9idGFpbj88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBpbnB1dCBsaW5lIGNvbnRhaW5zIGFuIGludGVnZXIgbi48XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBpbnB1dCBsaW5lIGNvbnRhaW5zIG4gaW50ZWdlcnM6IHRoZSBudW1iZXJzIGluIHRoZSBzZXF1ZW5jZTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdSBzaG91bGQgb3V0cHV0IG4gaW50ZWdlcnM6IHRoZSBsZXhpY29ncmFwaGljYWxseSBtaW5pbWFsIHNlcXVlbmNlLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2giLCJzdWJ0YXNrMSI6Ijx1bD5cclxuXHQ8bGk+MSAmbGU7IG4gJmxlOyAyMDxcL2xpPlxyXG48XC91bD5cclxuIiwic3VidGFzazIiOiI8dWw+XHJcblx0PGxpPjEgJmxlOyBuICZsZTsgNDA8XC9saT5cclxuPFwvdWw+XHJcbiIsInN1YnRhc2szIjoiPHVsPlxyXG5cdDxsaT4xICZsZTsgbiAmbGU7IDEwMDA8XC9saT5cclxuPFwvdWw+XHJcbiIsInN1YnRhc2s0IjoiPHVsPlxyXG5cdDxsaT4xICZsZTsgbiAmbGU7IDUgJnNkb3Q7IDEwPHN1cD40PFwvc3VwPjxcL2xpPlxyXG48XC91bD5cclxuIiwic3VidGFzazUiOiI8dWw+XHJcblx0PGxpPjEgJmxlOyBuICZsZTsgMiAmc2RvdDsgMTA8c3VwPjU8XC9zdXA+PFwvbGk+XHJcbjxcL3VsPlxyXG4ifV0=

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2016 6번

  • 문제의 오타를 찾은 사람: doju
  • 문제를 번역한 사람: myungwoo

채점 및 기타 정보

  • 예제는 채점하지 않는다.