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. 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 = q[0]
if f == 4:
i, j = q[1:]
if isTransposed:
i, j = j, i
print(N * (xs[i] - 1) + ys[j] - 1)
elif f == 3:
isTransposed = not isTransposed
else:
i, j = q[1:]
if (f == 1) ^ isTransposed:
xs[i], xs[j] = xs[j], xs[i]
else:
ys[i], ys[j] = ys[j], ys[i]
This page is auto-translated from /nishio/PAST3I using DeepL. 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.