시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 27 14 13 56.522%

문제

많은 프로그래밍 언어는 라이브러리 함수를 이용해서 배열의 값을 정렬할 수 있다. 이 함수를 사용해서 정렬을 하려면, less(x,y)와 같은 비교 함수를 작성해야 한다.

less(x,y)는 정렬한 순서에서 x가 y의 앞에 온다면 true를 리턴하는 함수이다. 이러한 함수는 항상 이치에 맞아야 한다. 즉, 서로 다른 두 원소 x와 y에 대해서, less(x,y)와 less(y,x)중 하나만 true가 되어야 한다.

이 문제에서는 수열에서 도치가 발생하지 않은 경우에 정렬되었다고 한다. less(x,y)에 대한 도치란, 크기가 n인 배열 A에서 less(A[j], A[i]) = true (0 ≤ i < j < n)를 만족하는 경우이다. (less(A[i], A[j]) = false와 동등한 의미가 아니다)

안타깝게도 어떤 프로그래머는 이런 비교 함수를 신중하게 작성하지 않는다. 이러한 경우에는 절대로 수열을 정렬할 수 없는 경우가 생길수도 있다.

less함수의 결과가 모두 주어진다. 이때, 이 함수를 이용해서 정렬했을 때, 도치의 개수를 최소가 되는 순열을 구하는 프로그램을 작성하시오.

입력

각 테스트 케이스의 첫째 줄에는 배열의 크기 n이 주어진다. (1 ≤ n ≤ 18) 배열의 각 원소는 0번부터 n-1번까지 번호가 매겨져 있다. 다음 n개의 줄에는 길이가 n인 이진 문자열이 주어지며, i번째 줄의 j번째 숫자는 less(i,j)의 리턴값을 의미한다. (0은 false, 1은 true를 의미)

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서, 주어진 비교 함수로 정렬했을 때, 도치의 개수가 최소가 되는 순열을 출력한다. 그 다음 줄에는 그 순열에서 도치의 개수를 출력한다. 만약, 도치의 개수가 같은 순열이 여러 개인 경우에는 사전 순으로 앞서는 것을 출력한다.

예제 입력 1

4
0111
0000
0100
0110
3
011
011
011
6
101010
011010
110110
000000
111010
001010
0

예제 출력 1

0 3 2 1
0
0 1 2
1
0 1 5 2 3 4
5
W3sicHJvYmxlbV9pZCI6IjQ4MDAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIzMDBcdWNkYTkgXHVjODE1XHViODJjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWI5Y2VcdWM3NDAgXHVkNTA0XHViODVjXHVhZGY4XHViNzk4XHViYzBkIFx1YzViOFx1YzViNFx1YjI5NCBcdWI3N2NcdWM3NzRcdWJlMGNcdWI3ZWNcdWI5YWMgXHVkNTY4XHVjMjE4XHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWJjMzBcdWM1ZjRcdWM3NTggXHVhYzEyXHVjNzQ0IFx1YzgxNVx1YjgyY1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM3NzQgXHVkNTY4XHVjMjE4XHViOTdjIFx1YzBhY1x1YzZhOVx1ZDU3NFx1YzExYyBcdWM4MTVcdWI4MmNcdWM3NDQgXHVkNTU4XHViODI0XHViYTc0LCBsZXNzKHgseSlcdWM2NDAgXHVhYzE5XHVjNzQwIFx1YmU0NFx1YWQ1MCBcdWQ1NjhcdWMyMThcdWI5N2MgXHVjNzkxXHVjMTMxXHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+bGVzcyh4LHkpXHViMjk0IFx1YzgxNVx1YjgyY1x1ZDU1YyBcdWMyMWNcdWMxMWNcdWM1ZDBcdWMxMWMgeFx1YWMwMCB5XHVjNzU4IFx1YzU1ZVx1YzVkMCBcdWM2MjhcdWIyZTRcdWJhNzQgdHJ1ZVx1Yjk3YyBcdWI5YWNcdWQxMzRcdWQ1NThcdWIyOTQgXHVkNTY4XHVjMjE4XHVjNzc0XHViMmU0LiBcdWM3NzRcdWI3ZWNcdWQ1NWMgXHVkNTY4XHVjMjE4XHViMjk0IFx1ZDU2ZFx1YzBjMSBcdWM3NzRcdWNlNThcdWM1ZDAgXHViOWRlXHVjNTQ0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVjOTg5LCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YjQ1MCBcdWM2ZDBcdWMxOGMgeFx1YzY0MCB5XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgbGVzcyh4LHkpXHVjNjQwIGxlc3MoeSx4KVx1YzkxMSBcdWQ1NThcdWIwOThcdWI5Y2MgdHJ1ZVx1YWMwMCBcdWI0MThcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzQgXHViYjM4XHVjODFjXHVjNWQwXHVjMTFjXHViMjk0IFx1YzIxOFx1YzVmNFx1YzVkMFx1YzExYyBcdWIzYzRcdWNlNThcdWFjMDAgXHViYzFjXHVjMGRkXHVkNTU4XHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWFjYmRcdWM2YjBcdWM1ZDAgXHVjODE1XHViODJjXHViNDE4XHVjNWM4XHViMmU0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gbGVzcyh4LHkpXHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWIzYzRcdWNlNThcdWI3ODAsIFx1ZDA2Y1x1YWUzMFx1YWMwMCBuXHVjNzc4IFx1YmMzMFx1YzVmNCBBXHVjNWQwXHVjMTFjIGxlc3MoQVtqXSwgQVtpXSkgPSB0cnVlICgwICZsZTsgaSAmbHQ7IGogJmx0OyBuKVx1Yjk3YyBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNzc0XHViMmU0LiAobGVzcyhBW2ldLCBBW2pdKSA9IGZhbHNlXHVjNjQwIFx1YjNkOVx1YjRmMVx1ZDU1YyBcdWM3NThcdWJiZjhcdWFjMDAgXHVjNTQ0XHViMmM4XHViMmU0KTxcL3A+XHJcblxyXG48cD5cdWM1NDhcdWQwYzBcdWFlNWRcdWFjOGNcdWIzYzQgXHVjNWI0XHViNWE0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1Yjc5OFx1YmEzOFx1YjI5NCBcdWM3NzRcdWI3ZjAgXHViZTQ0XHVhZDUwIFx1ZDU2OFx1YzIxOFx1Yjk3YyBcdWMyZTBcdWM5MTFcdWQ1NThcdWFjOGMgXHVjNzkxXHVjMTMxXHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gXHVjNzc0XHViN2VjXHVkNTVjIFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWM4MDhcdWIzMDBcdWI4NWMgXHVjMjE4XHVjNWY0XHVjNzQ0IFx1YzgxNVx1YjgyY1x1ZDU2MCBcdWMyMTggXHVjNWM2XHViMjk0IFx1YWNiZFx1YzZiMFx1YWMwMCBcdWMwZGRcdWFlMzhcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5sZXNzXHVkNTY4XHVjMjE4XHVjNzU4IFx1YWNiMFx1YWNmY1x1YWMwMCBcdWJhYThcdWI0NTAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1Yzc3NCBcdWQ1NjhcdWMyMThcdWI5N2MgXHVjNzc0XHVjNmE5XHVkNTc0XHVjMTFjIFx1YzgxNVx1YjgyY1x1ZDU4OFx1Yzc0NCBcdWI1NGMsIFx1YjNjNFx1Y2U1OFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDVjXHVjMThjXHVhYzAwIFx1YjQxOFx1YjI5NCBcdWMyMWNcdWM1ZjRcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YmMzMFx1YzVmNFx1Yzc1OCBcdWQwNmNcdWFlMzAgblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgbiAmbGU7IDE4KSBcdWJjMzBcdWM1ZjRcdWM3NTggXHVhYzAxIFx1YzZkMFx1YzE4Y1x1YjI5NCAwXHViYzg4XHViZDgwXHVkMTMwIG4tMVx1YmM4OFx1YWU0Y1x1YzljMCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViOWU0XHVhY2E4XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHViMmU0XHVjNzRjIG5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWUzOFx1Yzc3NFx1YWMwMCBuXHVjNzc4IFx1Yzc3NFx1YzljNCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwLCBpXHViYzg4XHVjOWY4IFx1YzkwNFx1Yzc1OCBqXHViYzg4XHVjOWY4IFx1YzIyYlx1Yzc5MFx1YjI5NCBsZXNzKGksailcdWM3NTggXHViOWFjXHVkMTM0XHVhYzEyXHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC4gKDBcdWM3NDAgZmFsc2UsIDFcdWM3NDAgdHJ1ZVx1Yjk3YyBcdWM3NThcdWJiZjgpPFwvcD5cclxuXHJcbjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0IDBcdWM3NzQgXHVkNTU4XHViMDk4IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1YzhmY1x1YzViNFx1YzljNCBcdWJlNDRcdWFkNTAgXHVkNTY4XHVjMjE4XHViODVjIFx1YzgxNVx1YjgyY1x1ZDU4OFx1Yzc0NCBcdWI1NGMsIFx1YjNjNFx1Y2U1OFx1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgXHVjZDVjXHVjMThjXHVhYzAwIFx1YjQxOFx1YjI5NCBcdWMyMWNcdWM1ZjRcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWFkZjggXHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFkZjggXHVjMjFjXHVjNWY0XHVjNWQwXHVjMTFjIFx1YjNjNFx1Y2U1OFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QsIFx1YjNjNFx1Y2U1OFx1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgXHVhYzE5XHVjNzQwIFx1YzIxY1x1YzVmNFx1Yzc3NCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWMwYWNcdWM4MDQgXHVjMjFjXHVjNzNjXHViODVjIFx1YzU1ZVx1YzExY1x1YjI5NCBcdWFjODNcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjQ4MDAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJBcHByb3hpbWF0ZSBTb3J0aW5nIiwiZGVzY3JpcHRpb24iOiI8cD5JbiBtYW55IHByb2dyYW1taW5nIGxhbmd1YWdlcywgbGlicmFyeSBmdW5jdGlvbnMgYXJlIHByb3ZpZGVkIGZvciBzb3J0aW5nIGVsZW1lbnRzIGluIGFuIGFycmF5LiBJbiBvcmRlciBmb3IgdGhlc2Ugc29ydGluZyBmdW5jdGlvbnMgdG8gd29yayBmb3IgZGlmZmVyZW50IHR5cGVzIG9mIGVsZW1lbnRzLCB0aGUgdXNlciBzdXBwbGllcyBhIGNvbXBhcmlzb24gZnVuY3Rpb24gbGVzcyh4LHkpIHdoaWNoIHJldHVybnMgdHJ1ZSBpZiBhbmQgb25seSBpZiB4IGNvbWVzIGJlZm9yZSB5IGluIHRoZSBzb3J0ZWQgb3JkZXIuIE9mIGNvdXJzZSwgdGhlIGNvbXBhcmlzb24gZnVuY3Rpb24gaGFzIHRvICYjMzk7bWFrZSBzZW5zZSYjMzk7LiBGb3IgZXhhbXBsZSwgZm9yIGFueSB0d28gZGlmZmVyZW50IGVsZW1lbnRzIHggYW5kIHksIGV4YWN0bHkgb25lIG9mIGxlc3MoeCx5KSBhbmQgbGVzcyh5LHgpIHNob3VsZCBiZSB0cnVlLiBGb3IgdGhlIHB1cnBvc2Ugb2YgdGhpcyBwcm9ibGVtLCBhbiBhcnJheSBpcyBzb3J0ZWQgd2hlbiB0aGVyZSBhcmUgbm8gaW52ZXJzaW9ucyB3aXRoIHJlc3BlY3QgdG8gdGhlIGNvbXBhcmlzb24gZnVuY3Rpb24uIEFuIGludmVyc2lvbiB3aXRoIHJlc3BlY3QgdG8gbGVzcyh4LHkpIGluIGFuIGFycmF5IEEgb2Ygc2l6ZSBuIChpbmRleGVkIGZyb20gMCkgaXMgYSBwYWlyIG9mIGludGVnZXJzIDAgJmxlOyBpICZsdDsgaiAmbHQ7IG4gc3VjaCB0aGF0IGxlc3MoQVtqXSwgQVtpXSkgPSB0cnVlIChub3RlIHRoYXQgdGhpcyBtYXkgbm90IGJlIGVxdWl2YWxlbnQgdG8gbGVzcyhBW2ldLCBBW2pdKSA9IGZhbHNlKS48XC9wPlxyXG5cclxuPHA+VW5mb3J0dW5hdGVseSwgc29tZSBwcm9ncmFtbWVycyBhcmUgbm90IHZlcnkgY2FyZWZ1bCBpbiBkZVx1ZmIwMW5pbmcgdGhlIGNvbXBhcmlzb24gZnVuY3Rpb24uIEluIHN1Y2ggY2FzZXMsIHRoZXJlIG1heSBiZSBubyB3YXkgdG8gc29ydCB0aGUgZWxlbWVudHMgaW4gYW4gYXJyYXkgdG8gc2F0aXNmeSB0aGUgY29tcGFyaXNvbiBmdW5jdGlvbi4gVGhlIGJlc3Qgd2UgY2FuIGRvIGlzIHRvIHByb2R1Y2UgYSBwZXJtdXRhdGlvbiBtaW5pbWl6aW5nIHRoZSBudW1iZXIgb2YgaW52ZXJzaW9ucyB3aXRoIHJlc3BlY3QgdG8gdGhlIGdpdmVuIGNvbXBhcmlzb24gZnVuY3Rpb24uPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5Gb3IgZWFjaCBjYXNlLCBhbiBpbnRlZ2VyIG4sIDEgJmxlOyBuICZsZTsgMTgsIGluZGljYXRpbmcgdGhlIHNpemUgb2YgdGhlIGFycmF5IGlzIGdpdmVuIG9uIG9uZSBsaW5lLiBUaGUgZWxlbWVudHMgaW4gdGhlIGFycmF5IGFyZSBsYWJlbGxlZCAwLCAxLCAyLCAuLi4sIG4tMS4gVGhlIG5leHQgbiBsaW5lcyBlYWNoIGNvbnRhaW5zIGEgYmluYXJ5IHN0cmluZyBvZiBsZW5ndGggbiwgd2l0aCB0aGUgaiB0aCBjaGFyYWN0ZXIgb2YgdGhlIGkgdGggbGluZSBpbmRpY2F0aW5nIHRoZSByZXN1bHQgb2YgdGhlIGNvbXBhcmlzb24gZnVuY3Rpb24gbGVzcyhpLCBqKSAoMCBtZWFucyBmYWxzZSBhbmQgMSBtZWFucyB0cnVlKS4gVGhlIGVuZCBvZiBpbnB1dCBpcyBpbmRpY2F0ZWQgYnkgYSBjYXNlIGluIHdoaWNoIG4gPSAwLiBUaGUgbGFzdCBjYXNlIHNob3VsZCBub3QgYmUgcHJvY2Vzc2VkLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGNhc2UsIG91dHB1dCB0aGUgcGVybXV0YXRpb24gdGhhdCBoYXMgdGhlIHNtYWxsZXN0IG51bWJlciBvZiBpbnZlcnNpb25zIHdpdGggcmVzcGVjdCB0byB0aGUgZ2l2ZW4gY29tcGFyaXNvbiBmdW5jdGlvbi4gVGhpcyBpcyBmb2xsb3dlZCBieSBhIGxpbmUgY29udGFpbmluZyBhIHNpbmdsZSBpbnRlZ2VyIGluZGljYXRpbmcgdGhlIG51bWJlciBvZiBpbnZlcnNpb25zIGluIHRoZSBwZXJtdXRhdGlvbi4gSWYgdGhlcmUgYXJlIG11bHRpcGxlIHBlcm11dGF0aW9ucyB3aXRoIHRoZSBzYW1lIG51bWJlciBvZiBpbnZlcnNpb25zLCBvdXRwdXQgdGhlIG9uZSB0aGF0IGlzIGxleGljb2dyYXBoaWNhbGx5IHNtYWxsZXN0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==