[BOJ 16927]回転配列2

12131 ワード

BOJ 16926配列回転1では、回転数Rが最大10910^9109に増加する.
  • 一番外側のケースは丸いキューになっています.このときQの大きさをQと呼びましょう
  • の回転数はRではなくQmod RQmod RQmodなので変換効率が高い.
  • は、再びクラブの前部からハウジングを充填する.
  • の内側のハウジングが存在しなくなるまで繰り返します.
  • したがって、回転シェルの関数を定義します.rotate_part(A, x1, y1, x2, y2, R) :A:NxM行列(x1, y1):行列の左上隅(x2, y2):行列の右下隅R:回転数
    また、内層に入るには、マトリクスの左上隅の座標値を1ずつ増加させ、右下隅の座標値を1ずつ減少させることができる.
    import sys
    #sys.stdin = open('input.txt', 'r')
    sys.setrecursionlimit(int(1e5))
    input = sys.stdin.readline
    
    from collections import deque
    
    def print_matrix(A, N, M):
        for i in range(N):
            for j in range(M):
                print(A[i][j], end=' ')
            print()
        print()
    
    def rotate_part(A, x1, y1, x2, y2, R):
        q = deque()
        for j in range(y1, y2):
            q.append(A[x1][j])
        for i in range(x1, x2):
            q.append(A[i][y2])
        for j in range(y2, y1, -1):
            q.append(A[x2][j])
        for i in range(x2, x1, -1):
            q.append(A[i][y1])
        
        Q = len(q)
        for _ in range(R % Q):
            element = q.popleft()
            q.append(element)
        
        for j in range(y1, y2):
            A[x1][j] = q.popleft()
        for i in range(x1, x2):
            A[i][y2] = q.popleft()
        for j in range(y2, y1, -1):
            A[x2][j] = q.popleft()
        for i in range(x2, x1, -1):
            A[i][y1] = q.popleft()
    
    
    N, M, R = map(int, input().split())
    A = []
    for _ in range(N):
        A.append(list(map(int, input().split())))
    
    for i in range(min(N, M) // 2):
        rotate_part(A, i, i, N - 1 - i, M - 1 - i, R)
    
    print_matrix(A, N, M)