RCO presents 日本橋ハーフマラソン 本戦 (オープン)

Submission #1174562

Source codeソースコード

# encoding: utf-8
import random, sys
import time
inputs = lambda: map(int, raw_input().split())

debug = sys.stderr.write

random.seed()

h, w, k, t = inputs()
X, Y = h, w
Cars = [inputs() for i in xrange(k)]
Coms = []

com_str = "LRUD-"
dd = [(0, -1), (0, 1), (-1, 0), (1, 0), (0, 0)]

order = range(k)
ds = range(4)

def dist(x0, y0, x1, y1):
    return abs(x0 - x1) + abs(y0 - y1)

# 整列
bucket = {}
for i in xrange(k):
    x0, y0, x1, y1 = Cars[i]
    bucket.setdefault(y1, []).append(i)
lidx = {} # 左index
ridx = {} # 右index
count = {}
for key in bucket:
    bucket[key].sort(key=lambda i: Cars[i][2])
    lidx[key] = 0
    ridx[key] = -1
    count[key] = 0

# まず整列
ready = set()
while len(ready) < k:
    random.shuffle(order)
    exist = {(x0, y0) for x0, y0, x1, y1 in Cars}
    coms = ["-"]*k

    lmi = min(lidx[key] for key in lidx if count[key] < len(bucket[key]))
    rmi = max(ridx[key] for key in ridx if count[key] < len(bucket[key]))
    for i in order:
        if i in ready:
            continue
        x0, y0, x1, y1 = Cars[i]
        lst = bucket[y1]

        g = None
        if lst[lidx[y1]] == i:
            g = (lidx[y1], y1)
        elif lst[ridx[y1]] == i:
            g = (X+ridx[y1], y1)

        random.shuffle(ds)
        if g is None:
            wild = 1
        else:
            wild = random.randint(0, 1)

        for d in ds:
            dx, dy = dd[d]
            nx = x0 + dx; ny = y0 + dy
            if not 0 < nx <= X or not 0 < ny <= Y:
                continue
            if not wild and dist(x0, y0, g[0]+1, g[1]) <= dist(nx, ny, g[0]+1, g[1]):
                continue
            if g is None:
                if nx-1 < lidx[ny] + 5 and d == 2:
                    continue
                if X + ridx[ny] - 5 < nx-1 and d == 3:
                    continue
            else:
                if not g[1] - 2 < ny < g[1] + 2:
                    if nx-1 < lidx[ny] + 3 and d == 2:
                        continue
                    if X + ridx[ny] - 3 < nx-1 and d == 3:
                        continue

            if (nx, ny) not in exist:
                exist.add((nx, ny))
                Cars[i] = (nx, ny, x1, y1)
                coms[i] = com_str[d]
                if g is not None and nx == g[0]+1 and ny == g[1]:
                    if not lmi+2 < nx-1 < X+rmi-2:
                        #debug("%d: ready %d (%d, %d)\n" % (len(Coms), i, nx, ny))
                        ready.add(i)
                        if lst[lidx[y1]] == i:
                            if lidx[y1] < len(lst)/2:
                                lidx[y1] += 1
                            count[y1] += 1
                        else:
                            if len(lst)+ridx[y1] > len(lst)/2+1:
                                ridx[y1] -= 1
                            count[y1] += 1
                break

    Coms.append("".join(coms))

# 最後に進んで配置
update = 1
while update:
    update = 0
    exist = {(x0, y0) for x0, y0, x1, y1 in Cars}
    coms = ["-"]*k
    for i in xrange(k):
        x0, y0, x1, y1 = Cars[i]
        if x0 < x1:
            nx = x0 + 1
            if (nx, y0) not in exist:
                Cars[i] = (nx, y0, x1, y1)
                coms[i] = "D"
                exist.add((nx, y0))
                update = 1
        elif x1 < x0:
            nx = x0 - 1
            if (nx, y0) not in exist:
                Cars[i] = (nx, y0, x1, y1)
                coms[i] = "U"
                exist.add((nx, y0))
                update = 1
    Coms.append("".join(coms))

sys.stdout.write("%d\n" % len(Coms))
sys.stdout.write("\n".join(Coms))

Submission

Task問題 B - 日本橋大渋滞
User nameユーザ名 tjake
Created time投稿日時
Language言語 Python2 (2.7.6)
Status状態 AC
Score得点 673980
Source lengthソースコード長 3755 Byte
File nameファイル名
Exec time実行時間 2195 ms
Memory usageメモリ使用量 6120 KB

Test case

Set

Set name Score得点 / Max score Cases
test_01 23442 / 50000 subtask_01_01.txt
test_02 24391 / 50000 subtask_01_02.txt
test_03 22183 / 50000 subtask_01_03.txt
test_04 21950 / 50000 subtask_01_04.txt
test_05 23289 / 50000 subtask_01_05.txt
test_06 23332 / 50000 subtask_01_06.txt
test_07 22134 / 50000 subtask_01_07.txt
test_08 22707 / 50000 subtask_01_08.txt
test_09 20886 / 50000 subtask_01_09.txt
test_10 22372 / 50000 subtask_01_10.txt
test_11 23630 / 50000 subtask_01_11.txt
test_12 21115 / 50000 subtask_01_12.txt
test_13 22543 / 50000 subtask_01_13.txt
test_14 24027 / 50000 subtask_01_14.txt
test_15 21692 / 50000 subtask_01_15.txt
test_16 23398 / 50000 subtask_01_16.txt
test_17 22322 / 50000 subtask_01_17.txt
test_18 21487 / 50000 subtask_01_18.txt
test_19 21617 / 50000 subtask_01_19.txt
test_20 21478 / 50000 subtask_01_20.txt
test_21 23354 / 50000 subtask_01_21.txt
test_22 19501 / 50000 subtask_01_22.txt
test_23 22728 / 50000 subtask_01_23.txt
test_24 22223 / 50000 subtask_01_24.txt
test_25 22584 / 50000 subtask_01_25.txt
test_26 22800 / 50000 subtask_01_26.txt
test_27 22037 / 50000 subtask_01_27.txt
test_28 22282 / 50000 subtask_01_28.txt
test_29 22968 / 50000 subtask_01_29.txt
test_30 23508 / 50000 subtask_01_30.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
subtask_01_01.txt AC 1773 ms 6120 KB
subtask_01_02.txt AC 1757 ms 4596 KB
subtask_01_03.txt AC 2021 ms 4980 KB
subtask_01_04.txt AC 1847 ms 4980 KB
subtask_01_05.txt AC 1691 ms 4724 KB
subtask_01_06.txt AC 1904 ms 4724 KB
subtask_01_07.txt AC 1937 ms 4980 KB
subtask_01_08.txt AC 1855 ms 4852 KB
subtask_01_09.txt AC 2129 ms 5108 KB
subtask_01_10.txt AC 1879 ms 4852 KB
subtask_01_11.txt AC 1764 ms 4724 KB
subtask_01_12.txt AC 2195 ms 5108 KB
subtask_01_13.txt AC 1988 ms 4852 KB
subtask_01_14.txt AC 1741 ms 4724 KB
subtask_01_15.txt AC 2068 ms 4980 KB
subtask_01_16.txt AC 1797 ms 4724 KB
subtask_01_17.txt AC 1867 ms 4852 KB
subtask_01_18.txt AC 1979 ms 4980 KB
subtask_01_19.txt AC 1920 ms 4980 KB
subtask_01_20.txt AC 2124 ms 4980 KB
subtask_01_21.txt AC 1886 ms 4724 KB
subtask_01_22.txt AC 1949 ms 5364 KB
subtask_01_23.txt AC 1886 ms 4852 KB
subtask_01_24.txt AC 1956 ms 4980 KB
subtask_01_25.txt AC 1970 ms 4852 KB
subtask_01_26.txt AC 1975 ms 4852 KB
subtask_01_27.txt AC 1850 ms 4980 KB
subtask_01_28.txt AC 1993 ms 4852 KB
subtask_01_29.txt AC 2010 ms 4852 KB
subtask_01_30.txt AC 1822 ms 4724 KB