Submission #18589909


Source Code Expand

Copy
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def from_read(dtype=np.int64):
    return np.fromstring(read().decode(), dtype=dtype, sep=' ')


def from_readline(dtype=np.int64):
    return np.fromstring(readline().decode(), dtype=dtype, sep=' ')

def main(A):
    N = len(A)
    if N == 2:
        if A[0] == 0:
            return []
        else:
            return [0]

    ans = []
    pos = np.zeros_like(A)
    for i in range(N):
        pos[A[i]] = i
    inv = np.zeros((N, N), np.int64)
    for i in range(3, N):
        for j in range(i + 1, N):
            pi = (pos[i] - pos[0]) % N
            pj = (pos[j] - pos[0]) % N
            if pi > pj:
                inv[i, j] = inv[j, i] = 1
    rest = inv.sum() // 2

    def ope_i(i):
        nonlocal ans, A, pos
        ans.append(i)
        j = (i + A[i]) % N
        A[i], A[j] = A[j], A[i]
        pos[A[i]] = i
        pos[A[j]] = j

    def ope_x(x):
        nonlocal ans, A, pos
        ope_i(pos[x])

    # 1 を 2 の手前に移動
    while (pos[1] + 1) % N != pos[2]:
        ope_x(1)
    while rest:
        i, j = pos[1], pos[2]
        k = (j + 1) % N
        l = (k + 1) % N
        x, y = A[k], A[l]
        if inv[x, y]:
            ope_x(2)
            ope_x(1)
            ope_x(1)
            inv[x, y] = inv[y, x] = 0
            rest -= 1
        else:
            ope_x(1)
            ope_x(2)
    while pos[2] != (pos[0] + 2) % N:
        ope_x(1)
        ope_x(2)
    while A[0] != 0 or A[1] != 1 or A[2] != 2:
        ope_x(1)
    return ans

def simulate(A, ans):
    N = len(A)
    for i in ans:
        j = (i + A[i]) % N
        A[i], A[j] = A[j], A[i]
    return A

A = from_read()[1:]

ans = main(A.copy())
# simulate(A, ans)

simulate(A, ans)

print(len(ans))
print('\n'.join(map(str, ans)))

Submission Info

Submission Time
Task F - Esoswap
User maspy
Language Python (3.8.2)
Score 900
Code Size 1961 Byte
Status AC
Exec Time 224 ms
Memory 30052 KB

Judge Result

Set Name All Sample
Score / Max Score 900 / 900 0 / 0
Status
AC × 53
AC × 1
Set Name Test Cases
All sample_01.txt, testcase_1.txt, testcase_10.txt, testcase_11.txt, testcase_12.txt, testcase_13.txt, testcase_14.txt, testcase_15.txt, testcase_16.txt, testcase_17.txt, testcase_18.txt, testcase_19.txt, testcase_2.txt, testcase_20.txt, testcase_21.txt, testcase_22.txt, testcase_23.txt, testcase_24.txt, testcase_25.txt, testcase_26.txt, testcase_27.txt, testcase_28.txt, testcase_29.txt, testcase_3.txt, testcase_30.txt, testcase_31.txt, testcase_32.txt, testcase_33.txt, testcase_34.txt, testcase_35.txt, testcase_36.txt, testcase_37.txt, testcase_38.txt, testcase_39.txt, testcase_4.txt, testcase_40.txt, testcase_41.txt, testcase_42.txt, testcase_43.txt, testcase_44.txt, testcase_45.txt, testcase_46.txt, testcase_47.txt, testcase_48.txt, testcase_49.txt, testcase_5.txt, testcase_50.txt, testcase_51.txt, testcase_52.txt, testcase_6.txt, testcase_7.txt, testcase_8.txt, testcase_9.txt
Sample sample_01.txt
Case Name Status Exec Time Memory
sample_01.txt AC 125 ms 27116 KB
testcase_1.txt AC 118 ms 27016 KB
testcase_10.txt AC 208 ms 29340 KB
testcase_11.txt AC 194 ms 29108 KB
testcase_12.txt AC 199 ms 28964 KB
testcase_13.txt AC 198 ms 28904 KB
testcase_14.txt AC 182 ms 28576 KB
testcase_15.txt AC 205 ms 29252 KB
testcase_16.txt AC 204 ms 29356 KB
testcase_17.txt AC 196 ms 28876 KB
testcase_18.txt AC 116 ms 26952 KB
testcase_19.txt AC 194 ms 29080 KB
testcase_2.txt AC 119 ms 26840 KB
testcase_20.txt AC 194 ms 28828 KB
testcase_21.txt AC 132 ms 27488 KB
testcase_22.txt AC 216 ms 29928 KB
testcase_23.txt AC 123 ms 27032 KB
testcase_24.txt AC 126 ms 27040 KB
testcase_25.txt AC 118 ms 27092 KB
testcase_26.txt AC 179 ms 28408 KB
testcase_27.txt AC 181 ms 28404 KB
testcase_28.txt AC 183 ms 28192 KB
testcase_29.txt AC 212 ms 29476 KB
testcase_3.txt AC 215 ms 29520 KB
testcase_30.txt AC 213 ms 29696 KB
testcase_31.txt AC 179 ms 28484 KB
testcase_32.txt AC 181 ms 28576 KB
testcase_33.txt AC 179 ms 28580 KB
testcase_34.txt AC 196 ms 28944 KB
testcase_35.txt AC 213 ms 29712 KB
testcase_36.txt AC 181 ms 28396 KB
testcase_37.txt AC 182 ms 28340 KB
testcase_38.txt AC 180 ms 28372 KB
testcase_39.txt AC 214 ms 29704 KB
testcase_4.txt AC 201 ms 29372 KB
testcase_40.txt AC 214 ms 30052 KB
testcase_41.txt AC 178 ms 28584 KB
testcase_42.txt AC 177 ms 28368 KB
testcase_43.txt AC 210 ms 29564 KB
testcase_44.txt AC 210 ms 29436 KB
testcase_45.txt AC 210 ms 29860 KB
testcase_46.txt AC 177 ms 28372 KB
testcase_47.txt AC 217 ms 29512 KB
testcase_48.txt AC 210 ms 29692 KB
testcase_49.txt AC 177 ms 28476 KB
testcase_5.txt AC 197 ms 29032 KB
testcase_50.txt AC 211 ms 29688 KB
testcase_51.txt AC 192 ms 29036 KB
testcase_52.txt AC 194 ms 29204 KB
testcase_6.txt AC 224 ms 30040 KB
testcase_7.txt AC 189 ms 28764 KB
testcase_8.txt AC 199 ms 28688 KB
testcase_9.txt AC 213 ms 29960 KB