QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#794964#7960. 排序大师thelongXiaoWA 12ms10808kbPython3820b2024-11-30 17:09:492024-11-30 17:09:49

Judging History

你现在查看的是最新测评结果

  • [2024-11-30 17:09:49]
  • 评测
  • 测评结果:WA
  • 用时:12ms
  • 内存:10808kb
  • [2024-11-30 17:09:49]
  • 提交

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]