提出 #42958370

ソースコード 拡げる

from copy import deepcopy
import random

def random_bool():
    return random.choice([True, False])
  
def biased_random_bool(a):
    if a == True:
    	return random.choices([True, False], weights=[0.9, 0.1])[0]
    return random.choices([True, False], weights=[0.1, 0.9])[0]

def swap_balls(N, balls, use_reverse_default=False, reverse1=True, reverse2=True):
    swaps = []
    swap_iteration_count = 1
    while swap_iteration_count > 0:
        swap_iteration_count = 0
        if use_reverse_default == False:
            reverse1 = biased_random_bool(reverse1)
            reverse2 = biased_random_bool(reverse2)
        for x in range(N-1):
            if reverse1:
                x = N-2-x
            for y in range(x+1):
                if reverse2:
                    y = x-y
                nx = x
                ny = y
                
                if balls[x+1][y] > balls[x+1][y+1]:
                    if balls[x][y] > balls[x+1][y+1]:
                        nx = x+1
                        ny = y+1  
                else:
                    if balls[x][y] > balls[x+1][y]:
                        nx = x+1
                        ny = y
                if x != nx:
                    swaps.append(((x, y), (nx, ny)))
                    balls[x][y], balls[nx][ny] = balls[nx][ny], balls[x][y]
                    swap_iteration_count += 1

    # 入れ替え操作の回数とリストを返す
    return len(swaps), swaps

# テスト用データ
N = 30
balls = [list(map(int, input().split())) for _ in range(N)]

pairs = [swap_balls(N, deepcopy(balls), False, random_bool(), random_bool()) for _ in range(250)]
pairs.append(swap_balls(N, deepcopy(balls), True, False, True))
pairs.append(swap_balls(N, deepcopy(balls), True, False, False))
pairs.append(swap_balls(N, deepcopy(balls), True, True, True))
pairs.append(swap_balls(N, deepcopy(balls), True, True, False))

min_pair = min(pairs, key=lambda pair: pair[0])

print(min_pair[0])
for swap in min_pair[1]:
    print(*swap[0], *swap[1])

提出情報

提出日時
問題 A - Pyramid Sorting
ユーザ tubotu
言語 Python (3.8.2)
得点 13043935
コード長 2082 Byte
結果 AC
実行時間 1620 ms
メモリ 170820 KiB

ジャッジ結果

セット名 test_ALL
得点 / 配点 13043935 / 15000000
結果
AC × 150
セット名 テストケース
test_ALL test_0000.txt, test_0001.txt, test_0002.txt, test_0003.txt, test_0004.txt, test_0005.txt, test_0006.txt, test_0007.txt, test_0008.txt, test_0009.txt, test_0010.txt, test_0011.txt, test_0012.txt, test_0013.txt, test_0014.txt, test_0015.txt, test_0016.txt, test_0017.txt, test_0018.txt, test_0019.txt, test_0020.txt, test_0021.txt, test_0022.txt, test_0023.txt, test_0024.txt, test_0025.txt, test_0026.txt, test_0027.txt, test_0028.txt, test_0029.txt, test_0030.txt, test_0031.txt, test_0032.txt, test_0033.txt, test_0034.txt, test_0035.txt, test_0036.txt, test_0037.txt, test_0038.txt, test_0039.txt, test_0040.txt, test_0041.txt, test_0042.txt, test_0043.txt, test_0044.txt, test_0045.txt, test_0046.txt, test_0047.txt, test_0048.txt, test_0049.txt, test_0050.txt, test_0051.txt, test_0052.txt, test_0053.txt, test_0054.txt, test_0055.txt, test_0056.txt, test_0057.txt, test_0058.txt, test_0059.txt, test_0060.txt, test_0061.txt, test_0062.txt, test_0063.txt, test_0064.txt, test_0065.txt, test_0066.txt, test_0067.txt, test_0068.txt, test_0069.txt, test_0070.txt, test_0071.txt, test_0072.txt, test_0073.txt, test_0074.txt, test_0075.txt, test_0076.txt, test_0077.txt, test_0078.txt, test_0079.txt, test_0080.txt, test_0081.txt, test_0082.txt, test_0083.txt, test_0084.txt, test_0085.txt, test_0086.txt, test_0087.txt, test_0088.txt, test_0089.txt, test_0090.txt, test_0091.txt, test_0092.txt, test_0093.txt, test_0094.txt, test_0095.txt, test_0096.txt, test_0097.txt, test_0098.txt, test_0099.txt, test_0100.txt, test_0101.txt, test_0102.txt, test_0103.txt, test_0104.txt, test_0105.txt, test_0106.txt, test_0107.txt, test_0108.txt, test_0109.txt, test_0110.txt, test_0111.txt, test_0112.txt, test_0113.txt, test_0114.txt, test_0115.txt, test_0116.txt, test_0117.txt, test_0118.txt, test_0119.txt, test_0120.txt, test_0121.txt, test_0122.txt, test_0123.txt, test_0124.txt, test_0125.txt, test_0126.txt, test_0127.txt, test_0128.txt, test_0129.txt, test_0130.txt, test_0131.txt, test_0132.txt, test_0133.txt, test_0134.txt, test_0135.txt, test_0136.txt, test_0137.txt, test_0138.txt, test_0139.txt, test_0140.txt, test_0141.txt, test_0142.txt, test_0143.txt, test_0144.txt, test_0145.txt, test_0146.txt, test_0147.txt, test_0148.txt, test_0149.txt
ケース名 結果 実行時間 メモリ
test_0000.txt AC 1584 ms 167136 KiB
test_0001.txt AC 1475 ms 151424 KiB
test_0002.txt AC 1525 ms 160996 KiB
test_0003.txt AC 1446 ms 152824 KiB
test_0004.txt AC 1405 ms 150948 KiB
test_0005.txt AC 1553 ms 163220 KiB
test_0006.txt AC 1537 ms 162696 KiB
test_0007.txt AC 1578 ms 163992 KiB
test_0008.txt AC 1460 ms 151928 KiB
test_0009.txt AC 1447 ms 153020 KiB
test_0010.txt AC 1457 ms 153368 KiB
test_0011.txt AC 1502 ms 157872 KiB
test_0012.txt AC 1514 ms 159044 KiB
test_0013.txt AC 1460 ms 155836 KiB
test_0014.txt AC 1620 ms 170660 KiB
test_0015.txt AC 1453 ms 155464 KiB
test_0016.txt AC 1537 ms 162068 KiB
test_0017.txt AC 1516 ms 160296 KiB
test_0018.txt AC 1496 ms 157856 KiB
test_0019.txt AC 1527 ms 162892 KiB
test_0020.txt AC 1511 ms 159920 KiB
test_0021.txt AC 1448 ms 153208 KiB
test_0022.txt AC 1463 ms 157356 KiB
test_0023.txt AC 1586 ms 165828 KiB
test_0024.txt AC 1468 ms 155256 KiB
test_0025.txt AC 1516 ms 160296 KiB
test_0026.txt AC 1504 ms 159424 KiB
test_0027.txt AC 1492 ms 157924 KiB
test_0028.txt AC 1557 ms 163492 KiB
test_0029.txt AC 1445 ms 151768 KiB
test_0030.txt AC 1519 ms 162224 KiB
test_0031.txt AC 1518 ms 163320 KiB
test_0032.txt AC 1531 ms 163284 KiB
test_0033.txt AC 1500 ms 159832 KiB
test_0034.txt AC 1459 ms 157052 KiB
test_0035.txt AC 1499 ms 159752 KiB
test_0036.txt AC 1502 ms 159644 KiB
test_0037.txt AC 1483 ms 155728 KiB
test_0038.txt AC 1529 ms 163404 KiB
test_0039.txt AC 1473 ms 154780 KiB
test_0040.txt AC 1445 ms 151632 KiB
test_0041.txt AC 1528 ms 163348 KiB
test_0042.txt AC 1579 ms 167404 KiB
test_0043.txt AC 1433 ms 152164 KiB
test_0044.txt AC 1467 ms 154816 KiB
test_0045.txt AC 1539 ms 162388 KiB
test_0046.txt AC 1469 ms 154480 KiB
test_0047.txt AC 1523 ms 163344 KiB
test_0048.txt AC 1514 ms 158292 KiB
test_0049.txt AC 1425 ms 151488 KiB
test_0050.txt AC 1547 ms 163132 KiB
test_0051.txt AC 1458 ms 155428 KiB
test_0052.txt AC 1444 ms 153488 KiB
test_0053.txt AC 1474 ms 152868 KiB
test_0054.txt AC 1522 ms 162280 KiB
test_0055.txt AC 1499 ms 162676 KiB
test_0056.txt AC 1459 ms 155812 KiB
test_0057.txt AC 1575 ms 163548 KiB
test_0058.txt AC 1566 ms 167760 KiB
test_0059.txt AC 1445 ms 154420 KiB
test_0060.txt AC 1560 ms 165612 KiB
test_0061.txt AC 1572 ms 164112 KiB
test_0062.txt AC 1536 ms 161924 KiB
test_0063.txt AC 1504 ms 158684 KiB
test_0064.txt AC 1500 ms 158792 KiB
test_0065.txt AC 1529 ms 160100 KiB
test_0066.txt AC 1494 ms 161136 KiB
test_0067.txt AC 1474 ms 157720 KiB
test_0068.txt AC 1523 ms 161212 KiB
test_0069.txt AC 1572 ms 165392 KiB
test_0070.txt AC 1397 ms 150828 KiB
test_0071.txt AC 1432 ms 151128 KiB
test_0072.txt AC 1499 ms 154952 KiB
test_0073.txt AC 1529 ms 160640 KiB
test_0074.txt AC 1481 ms 157440 KiB
test_0075.txt AC 1444 ms 153836 KiB
test_0076.txt AC 1515 ms 157376 KiB
test_0077.txt AC 1501 ms 159636 KiB
test_0078.txt AC 1499 ms 157260 KiB
test_0079.txt AC 1373 ms 150324 KiB
test_0080.txt AC 1586 ms 164692 KiB
test_0081.txt AC 1507 ms 158708 KiB
test_0082.txt AC 1398 ms 148580 KiB
test_0083.txt AC 1506 ms 160680 KiB
test_0084.txt AC 1518 ms 161640 KiB
test_0085.txt AC 1422 ms 152536 KiB
test_0086.txt AC 1483 ms 158320 KiB
test_0087.txt AC 1501 ms 159652 KiB
test_0088.txt AC 1483 ms 158080 KiB
test_0089.txt AC 1451 ms 157248 KiB
test_0090.txt AC 1522 ms 160016 KiB
test_0091.txt AC 1472 ms 155348 KiB
test_0092.txt AC 1519 ms 159820 KiB
test_0093.txt AC 1517 ms 162272 KiB
test_0094.txt AC 1556 ms 163464 KiB
test_0095.txt AC 1460 ms 155384 KiB
test_0096.txt AC 1510 ms 161536 KiB
test_0097.txt AC 1524 ms 163184 KiB
test_0098.txt AC 1536 ms 161380 KiB
test_0099.txt AC 1537 ms 161768 KiB
test_0100.txt AC 1428 ms 151164 KiB
test_0101.txt AC 1520 ms 161648 KiB
test_0102.txt AC 1520 ms 163324 KiB
test_0103.txt AC 1536 ms 163460 KiB
test_0104.txt AC 1520 ms 161056 KiB
test_0105.txt AC 1572 ms 167888 KiB
test_0106.txt AC 1551 ms 163564 KiB
test_0107.txt AC 1494 ms 161468 KiB
test_0108.txt AC 1459 ms 156600 KiB
test_0109.txt AC 1578 ms 164928 KiB
test_0110.txt AC 1466 ms 155940 KiB
test_0111.txt AC 1538 ms 164204 KiB
test_0112.txt AC 1487 ms 158332 KiB
test_0113.txt AC 1539 ms 158140 KiB
test_0114.txt AC 1553 ms 167800 KiB
test_0115.txt AC 1478 ms 154548 KiB
test_0116.txt AC 1450 ms 155036 KiB
test_0117.txt AC 1461 ms 155744 KiB
test_0118.txt AC 1500 ms 161716 KiB
test_0119.txt AC 1466 ms 156188 KiB
test_0120.txt AC 1550 ms 164568 KiB
test_0121.txt AC 1522 ms 160420 KiB
test_0122.txt AC 1461 ms 156188 KiB
test_0123.txt AC 1496 ms 160308 KiB
test_0124.txt AC 1560 ms 164832 KiB
test_0125.txt AC 1505 ms 163412 KiB
test_0126.txt AC 1464 ms 153912 KiB
test_0127.txt AC 1516 ms 161100 KiB
test_0128.txt AC 1465 ms 157008 KiB
test_0129.txt AC 1540 ms 163484 KiB
test_0130.txt AC 1449 ms 156060 KiB
test_0131.txt AC 1485 ms 157476 KiB
test_0132.txt AC 1614 ms 170820 KiB
test_0133.txt AC 1438 ms 152336 KiB
test_0134.txt AC 1557 ms 163512 KiB
test_0135.txt AC 1481 ms 159636 KiB
test_0136.txt AC 1507 ms 158684 KiB
test_0137.txt AC 1552 ms 165712 KiB
test_0138.txt AC 1485 ms 158676 KiB
test_0139.txt AC 1501 ms 158648 KiB
test_0140.txt AC 1442 ms 151628 KiB
test_0141.txt AC 1513 ms 161600 KiB
test_0142.txt AC 1500 ms 159756 KiB
test_0143.txt AC 1519 ms 160988 KiB
test_0144.txt AC 1522 ms 161228 KiB
test_0145.txt AC 1450 ms 156652 KiB
test_0146.txt AC 1517 ms 163212 KiB
test_0147.txt AC 1420 ms 152996 KiB
test_0148.txt AC 1491 ms 160572 KiB
test_0149.txt AC 1484 ms 156976 KiB