PAST3I
from Third Algorithm Practical Skills Test
PAST3I
The problem is to repeatedly execute commands such as transpose, row swap, column swap, display the value of a particular square, etc. on a square matrix.
Under the problem conditions, the maximum size of the matrix is 100,000, so we can see that naively having a matrix is not a viable option.
The first algorithm I thought of was "If you follow the time axis in reverse order from the display order, it is easy because you only have to think about one square.
However, after exceeding the time limit, he realizes that this is not good enough.
It was a simple enough program, and I realized that speeding it up with the algorithm as it was would not solve the problem.
It probably means "when the longest command sequence is 100,000 and about half of them are display commands, it takes about 1.2 billion steps".
With that in mind, we added that to the test case.
We will have the matrix broken down into the information "which row or column is the current row or column originally".
Transposition is a 1-bit flag is all that is needed.
code:python
if 1:
N = int(input())
Q = int(input())
queries = []
for i in range(Q):
queries.append(int(x) for x in input().split())
else:
N = 100000
queries = [
2, 1, 2,
4, 1, 2
] * 10000
queries.append(4, 1, 2)
Q = len(queries)
isTransposed = False
xs = list(range(N + 1))
ys = list(range(N + 1))
for q in queries:
f = q0
if f == 4:
i, j = q1:
if isTransposed:
i, j = j, i
print(N * (xsi - 1) + ysj - 1)
elif f == 3:
isTransposed = not isTransposed
else:
i, j = q1:
if (f == 1) ^ isTransposed:
xsi, xsj = xsj, xsi
else:
ysi, ysj = ysj, ysi
---
This page is auto-translated from /nishio/PAST3I. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I'm very happy to spread my thought to non-Japanese readers.