시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 4 4 4 100.000%

문제

상범 마법 팬케이크 하우스의 요리사는 가끔씩 팬케이크를 만들다가 잠에 빠진다. 그래서 쌓아둔 팬케이크의 한쪽이 종종 타버린다. 명백하게 탄 팬케이크를 서빙하는 건 좋은 생각이 아니다. 서빙하기 전에 웨이트리스는 팬케이크 더미를 배치해서 타버린 쪽이 아래를 향하도록 할 것이다. 또, 가장 위에는 크기가 제일 작은 팬케이크를, 가장 아래에는 크기가 제일 큰 팬케이크를 놓아 크기 순으로 정렬을 하려고 한다. 웨이트리스를 도와 올바르게 팬케이크를 쌓는 프로그램을 작성하시오.

우리는 한쪽면이 타버린 N개의 팬케이크 더미를 뒤집어야 한다. 우리가 위에서부터 k개의 팬케이크를 하나의 단위로 뒤집으면 맨 위에 있던 팬케이크는 k번째로 들어가고, k번째에 있던 팬케이크는 맨 위로 올라오게 된다.

예를 들면 다음과 같다.(+는 바닥이 탄 것, -는 위가 탄 것, 숫자는 팬케이크의 크기)

+1 -3 -2 [flip 2] => +3 -1 -2 [flip 1] => -3 -1 -2 [flip 3] => +2 +1 +3 [flip 1] => -2 +1 +3 [flip 2] => -1 +2 +3 [flip 1] => +1 +2 +3

최대 3n-2 번의 뒤집기(flip)한 수열을 찾는 프로그램을 만들어야 한다.

(수열의 처음과 마지막은 처음 주어진 상태와 아래가 모두 탄 팬케이크로 만든 상태가 된다)

입력

첫 줄에 테스트 케이스의 수 N이 입력으로 들어온다. 다음 N줄에는 각각의 줄에 팬케이크 수 M, 과 팬케이크의 크기(1~M)이 섞인 순서로 +또는 -부호를 달고 한번씩 등장한다. (M ≤ 30)

출력

각각의 케이스에 대해 한 줄씩 출력한다. 뒤집는 횟수 K(≥0), 한 번에 뒤집어야 하는 케이크 더미의 수 K개를 공백으로 구분하여 출력한다. 하나의 케이스에 대해 여러 개의 답이 존재할 수 있다. (예로 든 문제에서 3 2 3 또한 답이 될 수 있다.)

예제 입력 1

3
3 +1 -3 -2
4 -3 +1 -2 -4
5 +1 +2 +3 +4 -5

예제 출력 1

6 2 1 3 1 2 1
6 4 1 4 3 1 2
3 5 1 5
W3sicHJvYmxlbV9pZCI6IjI3MTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYzFcdWJjOTQgXHViOWM4XHViYzk1IFx1ZDMyY1x1Y2YwMFx1Yzc3NFx1ZDA2YyBcdWQ1NThcdWM2YjBcdWMyYTQiLCJkZXNjcmlwdGlvbiI6IjxwPlxyXG5cdFx1YzBjMVx1YmM5NCBcdWI5YzhcdWJjOTUgXHVkMzJjXHVjZjAwXHVjNzc0XHVkMDZjIFx1ZDU1OFx1YzZiMFx1YzJhNFx1Yzc1OCBcdWM2OTRcdWI5YWNcdWMwYWNcdWIyOTQgXHVhYzAwXHViMDU0XHVjNTI5IFx1ZDMyY1x1Y2YwMFx1Yzc3NFx1ZDA2Y1x1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWIyZTRcdWFjMDAgXHVjN2EwXHVjNWQwIFx1YmU2MFx1YzljNFx1YjJlNC4gXHVhZGY4XHViNzk4XHVjMTFjIFx1YzMxM1x1YzU0NFx1YjQ1NCBcdWQzMmNcdWNmMDBcdWM3NzRcdWQwNmNcdWM3NTggXHVkNTVjXHVjYWJkXHVjNzc0IFx1Yzg4NVx1Yzg4NSBcdWQwYzBcdWJjODRcdWI5YjBcdWIyZTQuIFx1YmE4NVx1YmMzMVx1ZDU1OFx1YWM4YyBcdWQwYzQgXHVkMzJjXHVjZjAwXHVjNzc0XHVkMDZjXHViOTdjIFx1YzExY1x1YmU1OVx1ZDU1OFx1YjI5NCBcdWFjNzQgXHVjODhiXHVjNzQwIFx1YzBkZFx1YWMwMVx1Yzc3NCBcdWM1NDRcdWIyYzhcdWIyZTQuIFx1YzExY1x1YmU1OVx1ZDU1OFx1YWUzMCBcdWM4MDRcdWM1ZDAgXHVjNmU4XHVjNzc0XHVkMmI4XHViOWFjXHVjMmE0XHViMjk0IFx1ZDMyY1x1Y2YwMFx1Yzc3NFx1ZDA2YyBcdWIzNTRcdWJiZjhcdWI5N2MgXHViYzMwXHVjZTU4XHVkNTc0XHVjMTFjIFx1ZDBjMFx1YmM4NFx1YjliMCBcdWNhYmRcdWM3NzQgXHVjNTQ0XHViNzk4XHViOTdjIFx1ZDVhNVx1ZDU1OFx1YjNjNFx1Yjg1ZCBcdWQ1NjAgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWI2MTAsIFx1YWMwMFx1YzdhNSBcdWM3MDRcdWM1ZDBcdWIyOTQgXHVkMDZjXHVhZTMwXHVhYzAwIFx1YzgxY1x1Yzc3YyBcdWM3OTFcdWM3NDAgXHVkMzJjXHVjZjAwXHVjNzc0XHVkMDZjXHViOTdjLCBcdWFjMDBcdWM3YTUgXHVjNTQ0XHViNzk4XHVjNWQwXHViMjk0IFx1ZDA2Y1x1YWUzMFx1YWMwMCBcdWM4MWNcdWM3N2MgXHVkMDcwIFx1ZDMyY1x1Y2YwMFx1Yzc3NFx1ZDA2Y1x1Yjk3YyBcdWIxOTNcdWM1NDQgXHVkMDZjXHVhZTMwIFx1YzIxY1x1YzczY1x1Yjg1YyBcdWM4MTVcdWI4MmNcdWM3NDQgXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNmU4XHVjNzc0XHVkMmI4XHViOWFjXHVjMmE0XHViOTdjIFx1YjNjNFx1YzY0MCBcdWM2MmNcdWJjMTRcdWI5NzRcdWFjOGMgXHVkMzJjXHVjZjAwXHVjNzc0XHVkMDZjXHViOTdjIFx1YzMxM1x1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM2YjBcdWI5YWNcdWIyOTQgXHVkNTVjXHVjYWJkXHViYTc0XHVjNzc0IFx1ZDBjMFx1YmM4NFx1YjliMCBOXHVhYzFjXHVjNzU4IFx1ZDMyY1x1Y2YwMFx1Yzc3NFx1ZDA2YyBcdWIzNTRcdWJiZjhcdWI5N2MgXHViNGE0XHVjOWQxXHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVjNmIwXHViOWFjXHVhYzAwIFx1YzcwNFx1YzVkMFx1YzExY1x1YmQ4MFx1ZDEzMCBrXHVhYzFjXHVjNzU4IFx1ZDMyY1x1Y2YwMFx1Yzc3NFx1ZDA2Y1x1Yjk3YyBcdWQ1NThcdWIwOThcdWM3NTggXHViMmU4XHVjNzA0XHViODVjIFx1YjRhNFx1YzlkMVx1YzczY1x1YmE3NCBcdWI5ZTggXHVjNzA0XHVjNWQwIFx1Yzc4OFx1YjM1OCBcdWQzMmNcdWNmMDBcdWM3NzRcdWQwNmNcdWIyOTQga1x1YmM4OFx1YzlmOFx1Yjg1YyBcdWI0ZTRcdWM1YjRcdWFjMDBcdWFjZTAsIGtcdWJjODhcdWM5ZjhcdWM1ZDAgXHVjNzg4XHViMzU4IFx1ZDMyY1x1Y2YwMFx1Yzc3NFx1ZDA2Y1x1YjI5NCBcdWI5ZTggXHVjNzA0XHViODVjIFx1YzYyY1x1Yjc3Y1x1YzYyNFx1YWM4YyBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWJhNzQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNC4oK1x1YjI5NCBcdWJjMTRcdWIyZTVcdWM3NzQgXHVkMGM0IFx1YWM4MywgLVx1YjI5NCBcdWM3MDRcdWFjMDAgXHVkMGM0IFx1YWM4MywgXHVjMjJiXHVjNzkwXHViMjk0IFx1ZDMyY1x1Y2YwMFx1Yzc3NFx1ZDA2Y1x1Yzc1OCBcdWQwNmNcdWFlMzApPFwvcD5cclxuPHA+XHJcblx0KzEgLTMgLTIgW2ZsaXAgMl0gPSZndDsgKzMgLTEgLTIgW2ZsaXAgMV0gPSZndDsgLTMgLTEgLTIgW2ZsaXAgM10gPSZndDsgKzIgKzEgKzMgW2ZsaXAgMV0gPSZndDsgLTIgKzEgKzMgW2ZsaXAgMl0gPSZndDsgLTEgKzIgKzMgW2ZsaXAgMV0gPSZndDsgKzEgKzIgKzM8XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjZDVjXHViMzAwIDNuLTIgXHViYzg4XHVjNzU4IFx1YjRhNFx1YzlkMVx1YWUzMChmbGlwKVx1ZDU1YyBcdWMyMThcdWM1ZjRcdWM3NDQgXHVjYzNlXHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcbjxwPlxyXG5cdChcdWMyMThcdWM1ZjRcdWM3NTggXHVjYzk4XHVjNzRjXHVhY2ZjIFx1YjljOFx1YzljMFx1YjljOVx1Yzc0MCBcdWNjOThcdWM3NGMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YzBjMVx1ZDBkY1x1YzY0MCBcdWM1NDRcdWI3OThcdWFjMDAgXHViYWE4XHViNDUwIFx1ZDBjNCBcdWQzMmNcdWNmMDBcdWM3NzRcdWQwNmNcdWI4NWMgXHViOWNjXHViNGUwIFx1YzBjMVx1ZDBkY1x1YWMwMCBcdWI0MWNcdWIyZTQpPFwvcD5cclxuXHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YzIxOCBOXHVjNzc0IFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWI0ZTRcdWM1YjRcdWM2MjhcdWIyZTQuIFx1YjJlNFx1Yzc0YyBOXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVkMzJjXHVjZjAwXHVjNzc0XHVkMDZjIFx1YzIxOCBNLCBcdWFjZmMgXHVkMzJjXHVjZjAwXHVjNzc0XHVkMDZjXHVjNzU4IFx1ZDA2Y1x1YWUzMCgxfk0pXHVjNzc0IFx1YzExZVx1Yzc3OCBcdWMyMWNcdWMxMWNcdWI4NWMgK1x1YjYxMFx1YjI5NCAtXHViZDgwXHVkNjM4XHViOTdjIFx1YjJlY1x1YWNlMCBcdWQ1NWNcdWJjODhcdWM1MjkgXHViNGYxXHVjN2E1XHVkNTVjXHViMmU0LiAoTSAmbGU7IDMwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0IFx1ZDU1YyBcdWM5MDRcdWM1MjkgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI0YTRcdWM5ZDFcdWIyOTQgXHVkNjlmXHVjMjE4IEsoJmdlOzApLCBcdWQ1NWMgXHViYzg4XHVjNWQwIFx1YjRhNFx1YzlkMVx1YzViNFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVjZjAwXHVjNzc0XHVkMDZjIFx1YjM1NFx1YmJmOFx1Yzc1OCBcdWMyMTggS1x1YWMxY1x1Yjk3YyBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHVkNTU4XHVjNWVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVkNTU4XHViMDk4XHVjNzU4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWIyZjVcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIChcdWM2MDhcdWI4NWMgXHViNGUwIFx1YmIzOFx1YzgxY1x1YzVkMFx1YzExYyAzIDIgMyBcdWI2MTBcdWQ1NWMgXHViMmY1XHVjNzc0IFx1YjQyMCBcdWMyMTggXHVjNzg4XHViMmU0Lik8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyNzE1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRmxpcHBpbmcgQnVybmVkIFBhbmNha2VzIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgY29vayBhdCB0aGUgRnJvYmJvenogTWFnaWMgUGFuY2FrZSBIb3VzZSBzb21ldGltZXMgZmFsbHMgYXNsZWVwIG9uIHRoZSBqb2Igd2hpbGUgY29va2luZyBwYW5jYWtlcy4gQXMgYSByZXN1bHQsIG9uZSBzaWRlIG9mIGEgc3RhY2sgb2YgcGFuY2FrZXMgaXMgb2Z0ZW4gYnVybmVkLiBDbGVhcmx5LCBpdCBpcyBiYWQgYnVzaW5lc3MgdG8gc2VydmUgdmlzaWJseSBidXJuZWQgcGFuY2FrZXMgdG8gdGhlIHBhdHJvbnMuIEJlZm9yZSBzZXJ2aW5nLCB0aGUgd2FpdHJlc3Mgd2lsbCBhcnJhbmdlIHRoZSBzdGFja3Mgb2YgcGFuY2FrZXMgc28gdGhhdCB0aGUgYnVybmVkIHNpZGVzIGFyZSBmYWNpbmcgZG93bi4gWW91IG11c3Qgd3JpdGUgYSBwcm9ncmFtIHRvIGFpZCB0aGUgd2FpdHJlc3MgaW4gc3RhY2tpbmcgdGhlIHBhbmNha2VzIGNvcnJlY3RseS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V2Ugc3RhcnQgd2l0aCBhIHN0YWNrIG9mIE4gcGFuY2FrZXMgb2YgZGlzdGluY3Qgc2l6ZXMsIGVhY2ggb2Ygd2hpY2ggaXMgYnVybmVkIG9uIG9uZSBzaWRlLiBUaGUgcHJvYmxlbSBpcyB0byBjb252ZXJ0IHRoZSBzdGFjayB0byBvbmUgaW4gd2hpY2ggdGhlIHBhbmNha2VzIGFyZSBpbiBzaXplIG9yZGVyIHdpdGggdGhlIHNtYWxsZXN0IG9uIHRoZSB0b3AgYW5kIHRoZSBsYXJnZXN0IG9uIHRoZSBib3R0b20gYW5kIGJ1cm5lZCBzaWRlIGRvd24gZm9yIGVhY2ggcGFuY2FrZS4gVG8gZG8gdGhpcywgd2UgYXJlIGFsbG93ZWQgdG8gZmxpcCB0aGUgdG9wIGsgcGFuY2FrZXMgb3ZlciBhcyBhIHVuaXQgKHNvIHRoZSBrLXRoIHBhbmNha2UgaXMgbm93IG9uIHRvcCBhbmQgdGhlIHBhbmNha2UgcHJldmlvdXNseSBvbiB0b3AgaXMgbm93IGluIHRoZSBrLXRoIHBvc2l0aW9uIGFuZCB0aGUgYnVybmVkIHNpZGUgZ29lcyBmcm9tIHRvcCB0byBib3R0b20gYW5kIHZpY2UgdmVyc2EpLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSAoKyBpbmRpY2F0ZXMgYnVybmVkIGJvdHRvbSwgLSBhIGJ1cm5lZCB0b3ApOiZuYnNwOzxcL3A+XHJcblxyXG48cD4rMSAtMyAtMiBbZmxpcCAyXSAmckFycjsgKzMgLTEgLTIgW2ZsaXAgMV0gJnJBcnI7IC0zIC0xIC0yIFtmbGlwIDNdICZyQXJyOzxiciBcLz5cclxuKzIgKzEgKzMgW2ZsaXAgMV0gJnJBcnI7IC0yICsxICszIFtmbGlwIDJdICZyQXJyOyAtMSArMiArMyBbZmxpcCAxXSAmckFycjsgKzEgKzIgKzMmbmJzcDs8XC9wPlxyXG5cclxuPHA+WW91IG11c3Qgd3JpdGUgYSBwcm9ncmFtIHdoaWNoIGZpbmRzIGEgc2VxdWVuY2Ugb2YgYXQgbW9zdCAoM24gJm5kYXNoOyAyKSBmbGlwcywgd2hpY2ggY29udmVydHMgYSBnaXZlbiBzdGFjayBvZiBwYW5jYWtlcyB0byBhIHNvcnRlZCBzdGFjayB3aXRoIGJ1cm5lZCBzaWRlcyBkb3duLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IGNvbnRhaW5zIGEgc2luZ2xlIGRlY2ltYWwgaW50ZWdlciwgTiwgdGhlIG51bWJlciBvZiBwcm9ibGVtIGluc3RhbmNlcyB0byBmb2xsb3cuIEVhY2ggb2YgdGhlIGZvbGxvd2luZyBOIGxpbmVzIGdpdmVzIGEgc2VwYXJhdGUgZGF0YXNldCBhcyBhIHNlcXVlbmNlIG9mIG51bWJlcnMgc2VwYXJhdGVkIGJ5IHNwYWNlcy4gVGhlIGZpcnN0IG51bWJlciBvbiBlYWNoIGxpbmUgZ2l2ZXMgdGhlIG51bWJlciwgTSwgb2YgcGFuY2FrZXMgaW4gdGhlIGRhdGEgc2V0LiBUaGUgcmVtYWluZGVyIG9mIHRoZSBkYXRhIHNldCBpcyB0aGUgbnVtYmVycyAxIHRocm91Z2ggTSBpbiBzb21lIG9yZGVyLCBlYWNoIHdpdGggYSBwbHVzIG9yIG1pbnVzIHNpZ24sIGdpdmluZyB0aGUgaW5pdGlhbCBwYW5jYWtlIHN0YWNrLiBUaGUgbnVtYmVycyBpbmRpY2F0ZSB0aGUgcmVsYXRpdmUgc2l6ZXMgb2YgdGhlIHBhbmNha2VzIGFuZCB0aGUgc2lnbnMgaW5kaWNhdGUgd2hldGhlciB0aGUgYnVybmVkIHNpZGUgaXMgdXAgKC0pIG9yIGRvd24gKCspLiBNIHdpbGwgYmUsIGF0IG1vc3QsIDMwLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGRhdGFzZXQsIHlvdSBzaG91bGQgZ2VuZXJhdGUgb25lIGxpbmUgb2Ygb3V0cHV0IHdpdGggdGhlIGZvbGxvd2luZyB2YWx1ZXM6IFRoZSBkYXRhc2V0IG51bWJlciBhcyBhIGRlY2ltYWwgaW50ZWdlciAoc3RhcnQgY291bnRpbmcgYXQgb25lKSwgYSBzcGFjZSwgdGhlIG51bWJlciBvZiBmbGlwcyAoSywgd2hlcmUgSyAmZ3Q7PSAwKSByZXF1aXJlZCB0byBzb3J0IHRoZSBwYW5jYWtlcyBhbmQgYSBzZXF1ZW5jZSBvZiBLIG51bWJlcnMsIGVhY2ggb2Ygd2hpY2ggZ2l2ZXMgdGhlIG51bWJlciBvZiBwYW5jYWtlcyB0byBmbGlwIG9uIHRoZSBjb3JyZXNwb25kaW5nIHNvcnRpbmcgc3RlcC4gVGhlcmUgbWF5IGJlIHNldmVyYWwgY29ycmVjdCBzb2x1dGlvbnMgZm9yIHNvbWUgZGF0YXNldHMuIEZvciBpbnN0YW5jZSAzIDIgMyBpcyBhbHNvIGEgc29sdXRpb24gdG8gdGhlIGZpcnN0IHByb2JsZW0gYmVsb3cuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d