시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
0.5 초 256 MB 19 13 10 71.429%

문제

크기가 N인 순열 A = [A1, A2, ..., AN]이 있을 때, 아래 코드를 이용하면 순열을 정리할 수 있다. 크기가 N인 순열은 1부터 N까지의 자연수가 한 번씩 등장하는 수열이다.

input: n, a[1 .. n]
cnt = 0
for j = 2 to n:
  x = a[j]
  i = j - 1
  while i >= 1 and a[i] > x:
    cnt = cnt + 1
    a[i+1] = a[i]
    i = i-1
  a[i+1] = x
의사코드

길이가 N인 순열을 정렬하는 경우 cnt는 항상 0 이상 N×(N-1)/2 이하이다. 두 정수 N과 M이 주어졌을 때, 위의 코드를 이용해 정렬이 완료된 후의 cnt의 값이 M이 되는 길이가 N인 순열을 찾아보자.

입력

첫째 줄에 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N과 M이 주어진다.

출력

각 테스트 케이스마다, 한 줄에 하나씩 cnt의 값이 M인 순열을 출력한다.

조건을 만족하는 순열이 여럿인 경우 아무 것이나 하나 출력하면 된다.

제한

  • 1 ≤ N ≤ 100,000
  • 0 ≤ M ≤ N×(N-1)/2

예제 입력 1

4
5 0
5 1
5 5
5 10

예제 출력 1

1 2 3 4 5
2 1 3 4 5
5 2 1 3 4
5 4 3 2 1
W3sicHJvYmxlbV9pZCI6IjE3NDMyIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjODE1XHViODJjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWQwNmNcdWFlMzBcdWFjMDAgTlx1Yzc3OCBcdWMyMWNcdWM1ZjQgQSA9IFtBPHN1Yj4xPFwvc3ViPiwgQTxzdWI+MjxcL3N1Yj4sIC4uLiwgQTxzdWI+TjxcL3N1Yj5dXHVjNzc0IFx1Yzc4OFx1Yzc0NCBcdWI1NGMsIFx1YzU0NFx1Yjc5OCBcdWNmNTRcdWI0ZGNcdWI5N2MgXHVjNzc0XHVjNmE5XHVkNTU4XHViYTc0IFx1YzIxY1x1YzVmNFx1Yzc0NCBcdWM4MTVcdWI5YWNcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4mbmJzcDtcdWQwNmNcdWFlMzBcdWFjMDAgTlx1Yzc3OCBcdWMyMWNcdWM1ZjRcdWM3NDAgMVx1YmQ4MFx1ZDEzMCBOXHVhZTRjXHVjOWMwXHVjNzU4IFx1Yzc5MFx1YzVmMFx1YzIxOFx1YWMwMCBcdWQ1NWMgXHViYzg4XHVjNTI5IFx1YjRmMVx1YzdhNVx1ZDU1OFx1YjI5NCBcdWMyMThcdWM1ZjRcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjx0YWJsZSBjbGFzcz1cInRhYmxlIHRhYmxlLWJvcmRlcmVkXCIgc3R5bGU9XCJ3aWR0aDogMTAwJTtcIj5cclxuXHQ8dGJvZHk+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZCBzdHlsZT1cIndpZHRoOiAxMDAlO1wiPlxyXG5cdFx0XHQ8cHJlPlxyXG5pbnB1dDogbiwgYVsxIC4uIG5dXHJcbmNudCA9IDBcclxuZm9yIGogPSAyIHRvIG46XHJcbiAmbmJzcDs8d2JyIFwvPnggPSBhW2pdXHJcbiAmbmJzcDs8d2JyIFwvPmkgPSBqIC0gMVxyXG4gJm5ic3A7PHdiciBcLz53aGlsZSBpICZndDs9IDEgYW5kIGFbaV0gJmd0OyB4OlxyXG4gJm5ic3A7PHdiciBcLz4gJm5ic3A7PHdiciBcLz5jbnQgPSBjbnQgKyAxXHJcbiAmbmJzcDs8d2JyIFwvPiAmbmJzcDs8d2JyIFwvPmFbaSsxXSA9IGFbaV1cclxuICZuYnNwOzx3YnIgXC8+ICZuYnNwOzx3YnIgXC8+aSA9IGktMVxyXG4gJm5ic3A7PHdiciBcLz5hW2krMV0gPSB4XHJcbjxcL3ByZT5cclxuXHRcdFx0PFwvdGQ+XHJcblx0XHRcdFxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ3aWR0aDogMTAwJTsgdGV4dC1hbGlnbjogY2VudGVyO1wiPlx1Yzc1OFx1YzBhY1x1Y2Y1NFx1YjRkYzxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGJvZHk+XHJcbjxcL3RhYmxlPlxyXG5cclxuPHA+XHVhZTM4XHVjNzc0XHVhYzAwIE5cdWM3NzggXHVjMjFjXHVjNWY0XHVjNzQ0IFx1YzgxNVx1YjgyY1x1ZDU1OFx1YjI5NCBcdWFjYmRcdWM2YjAgY250XHViMjk0IFx1ZDU2ZFx1YzBjMSAwIFx1Yzc3NFx1YzBjMSBOJnRpbWVzOyhOLTEpXC8yIFx1Yzc3NFx1ZDU1OFx1Yzc3NFx1YjJlNC4gXHViNDUwIFx1YzgxNVx1YzIxOCBOXHVhY2ZjIE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNzA0XHVjNzU4IFx1Y2Y1NFx1YjRkY1x1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NzQgXHVjODE1XHViODJjXHVjNzc0IFx1YzY0NFx1YjhjY1x1YjQxYyBcdWQ2YzRcdWM3NTggY250XHVjNzU4IFx1YWMxMlx1Yzc3NCBNXHVjNzc0IFx1YjQxOFx1YjI5NCBcdWFlMzhcdWM3NzRcdWFjMDAgTlx1Yzc3OCBcdWMyMWNcdWM1ZjRcdWM3NDQgXHVjYzNlXHVjNTQ0XHViY2Y0XHVjNzkwLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YzIxOCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVkNTVjIFx1YzkwNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwLCBOXHVhY2ZjIE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0LCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBjbnRcdWM3NTggXHVhYzEyXHVjNzc0IE1cdWM3NzggXHVjMjFjXHVjNWY0XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWMyMWNcdWM1ZjRcdWM3NzQgXHVjNWVjXHViN2ZmXHVjNzc4IFx1YWNiZFx1YzZiMCBcdWM1NDRcdWJiMzQgXHVhYzgzXHVjNzc0XHViMDk4IFx1ZDU1OFx1YjA5OCBcdWNkOWNcdWI4MjVcdWQ1NThcdWJhNzQgXHViNDFjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCIsImxpbWl0IjoiPHVsPlxyXG5cdDxsaT4xICZsZTsgTiAmbGU7IDEwMCwwMDA8XC9saT5cclxuXHQ8bGk+MCAmbGU7IE0gJmxlOyBOJnRpbWVzOyhOLTEpXC8yPFwvbGk+XHJcbjxcL3VsPlxyXG4ifSx7InByb2JsZW1faWQiOiIxNzQzMiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlNvcnRpbmciLCJkZXNjcmlwdGlvbiI6IjxwPkZvciBhbnkgcGVybXV0YXRpb24gQSBvZiBsZW5ndGggTiAoQSA9IFtBPHN1Yj4xPFwvc3ViPiwgQTxzdWI+MjxcL3N1Yj4sIC4uLiwgQTxzdWI+TjxcL3N1Yj5dKSwgd2UgY2FuIHNvcnQgQSB3aXRoIGFueSBvZiB0aGUgZm9sbG93aW5nIGNvZGUuPFwvcD5cclxuXHJcbjxwPkluIHRoaXMgcHJvYmxlbSwgYSBwZXJtdXRhdGlvbiBvZiBsZW5ndGggTiBpcyBhIHNlcXVlbmNlIG9mIG51bWJlcnMgd2hlcmUgZWFjaCBudW1iZXIgYmV0d2VlbiAxIGFuZCBOIGFwcGVhcnMgZXhhY3RseSBvbmNlLjxcL3A+XHJcblxyXG48dGFibGUgY2xhc3M9XCJ0YWJsZSB0YWJsZS1ib3JkZXJlZFwiIHN0eWxlPVwid2lkdGg6IDEwMCU7XCI+XHJcblx0PHRib2R5PlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ3aWR0aDogMTAwJTtcIj5cclxuXHRcdFx0PHByZT5cclxuaW5wdXQ6IG4sIGFbMSAuLiBuXVxyXG5jbnQgPSAwXHJcbmZvciBqID0gMiB0byBuOlxyXG4gJm5ic3A7PHdiciBcLz54ID0gYVtqXVxyXG4gJm5ic3A7PHdiciBcLz5pID0gaiAtIDFcclxuICZuYnNwOzx3YnIgXC8+d2hpbGUgaSAmZ3Q7PSAxIGFuZCBhW2ldICZndDsgeDpcclxuICZuYnNwOzx3YnIgXC8+ICZuYnNwOzx3YnIgXC8+Y250ID0gY250ICsgMVxyXG4gJm5ic3A7PHdiciBcLz4gJm5ic3A7PHdiciBcLz5hW2krMV0gPSBhW2ldXHJcbiAmbmJzcDs8d2JyIFwvPiAmbmJzcDs8d2JyIFwvPmkgPSBpLTFcclxuICZuYnNwOzx3YnIgXC8+YVtpKzFdID0geFxyXG48XC9wcmU+XHJcblx0XHRcdDxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZCBzdHlsZT1cIndpZHRoOiAxMDAlOyB0ZXh0LWFsaWduOiBjZW50ZXI7XCI+UHNldWRvY29kZTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGJvZHk+XHJcbjxcL3RhYmxlPlxyXG5cclxuPHA+V2hlbiBzb3J0IGEgcGVybXV0YXRpb24gb2YgbGVuZ3RoIE4sIGNudCB3aWxsIGFsd2F5cyBiZSBiZXR3ZWVuIDAgYW5kIE4mdGltZXM7KE4tMSlcLzIuIEdpdmVuIHR3byBpbnRlZ2VycyBOIGFuZCBNLCBmaW5kIGEgcGVybXV0YXRpb24gb2YgbGVuZ3RoIE4gc3VjaCB0aGF0IGlmIHdlIGFwcGx5IGFueSBvZiB0aGUgY29kZSBhYm92ZSB0aGUgZmluYWwgdmFsdWUgb2YgY250IHdpbGwgYmUgZXF1YWwgdG8gTS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIHdpbGwgY29udGFpbiBvbmUgaW50ZWdlciBULCB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMuPFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIG5leHQgVCBsaW5lcyB3aWxsIGNvbnRhaW4gdHdvIGludGVnZXJzIE4gYW5kIE0sIHNlcGFyYXRlZCBieSBhIHdoaXRlc3BhY2UuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBvdXRwdXQgYSBwZXJtdXRhdGlvbiBvZiBsZW5ndGggTiBzbyB0aGF0IGNudCB3b3VsZCBiZSBlcXVhbCB0byBNLjxcL3A+XHJcblxyXG48cD5JZiB0aGVyZSBleGlzdCBtdWx0aXBsZSBzdWNoIHBlcm11dGF0aW9ucywgeW91IG1heSBvdXRwdXQgYW55IG9uZSBvZiB0aGVtLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCIsImxpbWl0IjoiPHVsPlxyXG5cdDxsaT4xICZsZTsgTiAmbGU7IDEwMCwwMDA8XC9saT5cclxuXHQ8bGk+MCAmbGU7IE0gJmxlOyBOJnRpbWVzOyhOLTEpXC8yPFwvbGk+XHJcbjxcL3VsPlxyXG4ifV0=