QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#794964 | #7960. 排序大师 | thelongXiao | WA | 12ms | 10808kb | Python3 | 820b | 2024-11-30 17:09:49 | 2024-11-30 17:09:49 |
Judging History
answer
def To_minswaps(n, arr):
swaps = []
pos = [0] * n
#防止在寻找循环时重复访问同一个元素
v = [False] * n
# 初始化位置数组
for i in range(n):
pos[arr[i] - 1] = i
# 找到每个循环并执行交换
for i in range(n):
if not v[i]:
cycle = []
x = i
while not v[x]:
v[x] = True
cycle.append(x)
x = pos[x]
if len(cycle) > 1:
start = cycle[0] + 1
end = cycle[-1] + 1
swaps.append((start, end, start, end))
return swaps
n = int(input())
arr = list(map(int, input().split()))
swaps = To_minswaps(n, arr)
print(len(swaps))
for swap in swaps:
print(' '.join(map(str, swap)))
详细
Test #1:
score: 100
Accepted
time: 7ms
memory: 10716kb
input:
1 1
output:
0
result:
ok orz U R the sorting master!
Test #2:
score: -100
Wrong Answer
time: 12ms
memory: 10808kb
input:
1970 1452 1799 174 371 132 637 23 1510 1819 1794 1665 450 1183 564 1305 548 554 1310 701 1454 1843 1498 1040 1678 77 614 1928 1761 1718 1637 1853 1026 1804 1062 805 864 1859 586 663 346 335 681 152 1768 1639 1713 856 1401 1833 1350 1842 558 241 1829 802 581 1958 845 722 239 1793 1118 1251 1892 1949 ...
output:
9 1 1452 1 1452 2 1799 2 1799 18 1310 18 1310 21 1843 21 1843 30 1637 30 1637 31 1853 31 1853 39 663 39 663 42 681 42 681 58 845 58 845
result:
wrong answer Integer 1 violates the range [1453, 1970]