[BOJ 16927]回転配列2

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)