행렬만들기

• 사실 직관적으로 먼저 떠오르는 것은 네트워크 플로우 (Network Flow)를 이용한 풀이이다. 각 열에 해당하는 노드와, 각 행에 해당하는 노드를 만들어서 모두 연결해준다. 그리고 소스에서 각각의 열까지 엣지를 연결하고 캐퍼시티를 그 열의 1의 갯수로 지정해주고, 또 각 행에서 싱크까지 엣지를 연결하고 캐퍼시티를 그 행의 1의 갯수로 지정해준다. 이렇게 해서 최대 유량을 구하면 되긴 하는데.. |V|=O(n), |E|=O(n^2) 의 그래프에서 계산해야 하는지라 시간이 만만치 않다..
• 더 간단하고 빠른 그리디 알고리즘이 존재한다.
• 행 단위로 채워나간다고 생각해보자. i번째 행에 1의 갯수가 r[i] 개라고 하면, r[i]개의 열을 골라서 1로 채워야 한다는 뜻이다. 이 r[i]개의 열을 고를때.. 이미 i-1번째 행까지를 채우면서 그 열의 1 갯수만큼의 1을 모두 채워버린 열은 당연히 고를수가 없다. 남아있는 1의 갯수가 한개 이상인 열 중에서 골라야 하는데, 결론부터 말하면 남아있는 1의 갯수가 가장 많은 열부터 고르면 된다.
  • 남아있는 1의 갯수가 0, 2, 3 인데 이중에서 한개의 열을 골라서 1을 채워야 한다고 생각하자. 2번째 열을 골라서 남아있는 1의 갯수가 0, 1, 3 이 되어버린다면 이후 행에서 2개, 2개를 골라야 한다고 할때 채울수가 없다. 3번째 열을 골라서 남아있는 1의 갯수를 0,2,2로 만들면 이후 행에서 2개,2개를 고를수 있다. 일반적인 경우에서도, 남은 1의 갯수를 작은 순으로 정렬시켜서 얻은 시퀀스를 lexicographical 하게 비교했을때, 작은 쪽에서 채울수 있는 경우는 큰쪽에서도 항상 채울수 있다는 것을 쉽게 알수 있다 (증명 생략). 따라서 저 시퀀스를 최대화시키는 것이 최적 전략이다.
• 실제 구현하려면, 매 행을 계산할때마다, 각 열들중 최대값 n개를 구해야 하고, 그것들에 대해서 업데이트를 해주어야 한다. 결국 매번 O(nlogn)에 소팅을 해야하고 O(n)에 업데이트를 해야 하므로, 총 시간복잡도가 O(n^2logn)이 된다고 생각할수 있다. 그러나, 한번 소팅한다음에, 앞쪽 x개에 대해서만 남은 갯수를 1씩 줄이는 것이기 때문에, 앞쪽 x개 원소는 여전히 정렬 상태를 유지하고, 뒤쪽 n-x개 원소 역시 정렬되어있는 상태다. 따라서 다음 번에는 O(nlogn)의 소팅이 아니라 O(n)의 머지만으로도 충분하다. (파이썬의 timsort 알고리즘 덕분에 그냥 내장 sort를 호출해도 O(n)에 처리된다.) 따라서 전체 시간 복잡도는 O(nlogn) + O(n^2) = O(n^2) 이 된다.
• 답이 존재하는 경우에, 행렬을 출력하기 전에 먼저 '1'을 출력해야 한다는 것에 유의. 문제는 항상 꼼꼼히 읽어야 한다

"""Solution code for "BOJ 1960. 행렬만들기".

- Problem link: https://www.acmicpc.net/problem/1960
- Solution link: http://www.teferi.net/ps/problems/boj/1960

Tags: [Greedy]
"""


def main():
    n = int(input())
    count_by_row = [int(x) for x in input().split()]
    count_by_col = [int(x) for x in input().split()]

    answer = []
    sorted_cols = list(range(n))
    for count in count_by_row:
        answer_row = ['0'] * n
        sorted_cols.sort(reverse=True, key=count_by_col.__getitem__)
        for col in sorted_cols[:count]:
            count_by_col[col] -= 1
            answer_row[col] = '1'
        answer.append(''.join(answer_row))

    if all(x == 0 for x in count_by_col):
        print('1')
        print('\n'.join(answer))
    else:
        print('-1')


if __name__ == '__main__':
    main()