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

Submission #1174610

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 = {}
ref = [0]*k
for i in xrange(k):
    x0, y0, x1, y1 = Cars[i]
    bucket.setdefault(y1, []).append(i)
    ref[i] = len(bucket[y1])
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

# ランダムに散らしてみる
for _ in xrange(400):
    random.shuffle(order)
    exist = {(x0, y0) for x0, y0, x1, y1 in Cars}
    coms = ["-"]*k
    for i in order:
        random.shuffle(ds)
        wild = random.randint(0, 3)
        x0, y0, x1, y1 = Cars[i]

        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, x1, y1) <= dist(nx, ny, x1, y1):
                continue

            if (nx, ny) not in exist:
                exist.add((nx, ny))
                Cars[i] = (nx, ny, x1, y1)
                coms[i] = com_str[d]
                break
    Coms.append("".join(coms))

# まず整列
ready = set()
while len(ready) < k and len(Coms) < 2000:
    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 = random.randint(0, 5)
        else:
            wild = random.randint(0, 1)
            if len(ready) > k-10:
                wild = random.randint(0, 2) < 1

        xx = X/2 - len(lst)/2 + ref[i]
        yy = y1
        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:
                if g is not None:
                    if dist(x0, y0, g[0]+1, g[1]) <= dist(nx, ny, g[0]+1, g[1]):
                        continue
                else:
                    if dist(x0, y0, xx, yy) <= dist(nx, ny, xx, yy):
                        continue
            if g is None:
                if nx-1 < lidx[ny] + 3 and d == 2:
                    continue
                if X + ridx[ny] - 3 < nx-1 and d == 3:
                    continue
            else:
                if not g[1] - 2 < ny < g[1] + 2:
                    if nx-1 < lidx[ny] + 4 and d == 2:
                        continue
                    if X + ridx[ny] - 4 < nx-1 and d == 3:
                        continue
                else:
                    if nx-1 < lidx[y1] and d == 2:
                        continue
                    if X + ridx[ny] < 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+1 < nx-1 < X+rmi-1:
                        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得点 708757
Source lengthソースコード長 5051 Byte
File nameファイル名
Exec time実行時間 2628 ms
Memory usageメモリ使用量 6120 KB

Test case

Set

Set name Score得点 / Max score Cases
test_01 23867 / 50000 subtask_01_01.txt
test_02 25615 / 50000 subtask_01_02.txt
test_03 24619 / 50000 subtask_01_03.txt
test_04 24225 / 50000 subtask_01_04.txt
test_05 23354 / 50000 subtask_01_05.txt
test_06 23855 / 50000 subtask_01_06.txt
test_07 23878 / 50000 subtask_01_07.txt
test_08 23652 / 50000 subtask_01_08.txt
test_09 22462 / 50000 subtask_01_09.txt
test_10 24225 / 50000 subtask_01_10.txt
test_11 24534 / 50000 subtask_01_11.txt
test_12 22242 / 50000 subtask_01_12.txt
test_13 23343 / 50000 subtask_01_13.txt
test_14 24643 / 50000 subtask_01_14.txt
test_15 22915 / 50000 subtask_01_15.txt
test_16 23420 / 50000 subtask_01_16.txt
test_17 24237 / 50000 subtask_01_17.txt
test_18 22884 / 50000 subtask_01_18.txt
test_19 24225 / 50000 subtask_01_19.txt
test_20 23585 / 50000 subtask_01_20.txt
test_21 23890 / 50000 subtask_01_21.txt
test_22 21506 / 50000 subtask_01_22.txt
test_23 24498 / 50000 subtask_01_23.txt
test_24 22402 / 50000 subtask_01_24.txt
test_25 23821 / 50000 subtask_01_25.txt
test_26 23420 / 50000 subtask_01_26.txt
test_27 23000 / 50000 subtask_01_27.txt
test_28 23267 / 50000 subtask_01_28.txt
test_29 24120 / 50000 subtask_01_29.txt
test_30 23053 / 50000 subtask_01_30.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
subtask_01_01.txt AC 2269 ms 6120 KB
subtask_01_02.txt AC 2005 ms 4468 KB
subtask_01_03.txt AC 2190 ms 4596 KB
subtask_01_04.txt AC 2312 ms 4724 KB
subtask_01_05.txt AC 2265 ms 4852 KB
subtask_01_06.txt AC 2283 ms 4724 KB
subtask_01_07.txt AC 2234 ms 4724 KB
subtask_01_08.txt AC 2336 ms 4724 KB
subtask_01_09.txt AC 2464 ms 4980 KB
subtask_01_10.txt AC 2307 ms 4724 KB
subtask_01_11.txt AC 2262 ms 4596 KB
subtask_01_12.txt AC 2443 ms 4980 KB
subtask_01_13.txt AC 2495 ms 4852 KB
subtask_01_14.txt AC 2166 ms 4596 KB
subtask_01_15.txt AC 2520 ms 4852 KB
subtask_01_16.txt AC 2355 ms 4724 KB
subtask_01_17.txt AC 2274 ms 4724 KB
subtask_01_18.txt AC 2481 ms 4852 KB
subtask_01_19.txt AC 2301 ms 4724 KB
subtask_01_20.txt AC 2417 ms 4724 KB
subtask_01_21.txt AC 2314 ms 4724 KB
subtask_01_22.txt AC 2628 ms 5108 KB
subtask_01_23.txt AC 2278 ms 4596 KB
subtask_01_24.txt AC 2571 ms 4980 KB
subtask_01_25.txt AC 2270 ms 4724 KB
subtask_01_26.txt AC 2427 ms 4724 KB
subtask_01_27.txt AC 2398 ms 4852 KB
subtask_01_28.txt AC 2481 ms 4852 KB
subtask_01_29.txt AC 2269 ms 4724 KB
subtask_01_30.txt AC 2462 ms 4852 KB