Contest Duration: - (local time) (120 minutes) Back to Home

Submission #18589909

Source Code Expand

Copy
```import sys
import numpy as np

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

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

simulate(A, ans)

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

#### Submission Info

Submission Time 2020-12-05 22:15:16+0900 F - Esoswap maspy Python (3.8.2) 900 1961 Byte AC 224 ms 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