Submission #1173816


Source Code Expand

import random, sys
import time
inputs = lambda: map(int, raw_input().split())

random.seed()

h, w, k, t = inputs()
X, Y = w, h
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)
def calc_score(L, Cars):
    Pd = 20 + sum(abs(x0 - x1) + abs(y0 - y1) for x0, y0, x1, y1 in Cars)
    Pt = 10 + L * 0.01
    return 10**7 / (Pt * Pd)

L = 0
tries = 25
for l in xrange(t):
    current_score = calc_score(l, Cars)
    #print Cars, current_score
    next_score = current_score
    coms = [4]*k
    exist_ = {(x0, y0) for x0, y0, x1, y1 in Cars}
    for _ in xrange(tries):
        coms_tmp = [4]*k
        nCars = [e[:] for e in Cars]
        random.shuffle(order)
        exist = set(exist_)
        for i in order:
            x0, y0, x1, y1 = Cars[i]
            if x0 == x1 and y0 == y1:
                continue
            random.shuffle(ds)
            if random.randint(0, 15):
                for d in ds:
                    dx, dy = dd[d]
                    nx = x0 + dx; ny = y0 + dy
                    if not -1 < nx < X or not -1 < ny < Y:
                        continue
                    if dist(x0, y0, x1, y1) <= dist(nx, ny, x1, y1):
                        continue
                    if (nx, ny) not in exist:
                        exist.add((nx, ny))
                        nCars[i] = (nx, ny, x1, y1)
                        coms_tmp[i] = d
                        break
        score = calc_score(l+1, nCars)
        if next_score < score < current_score * 1.1:
            next_score = score
            coms = coms_tmp
    if current_score == next_score or l == 10000:
        L = l
        break
    for i in xrange(k):
        dx, dy = dd[coms[i]]
        x0, y0, x1, y1 = Cars[i]
        Cars[i] = (x0+dx, y0+dy, x1, y1)
    Coms.append(map(com_str.__getitem__, coms))
sys.stdout.write("%d\n" % L)
sys.stdout.write("\n".join("".join(e) for e in Coms))

Submission Info

Submission Time
Task B - 日本橋大渋滞
User yaketake08
Language Python (2.7.6)
Score 4611
Code Size 2111 Byte
Status AC
Exec Time 2984 ms
Memory 4840 KB

Judge Result

Set Name test_01 test_02 test_03 test_04 test_05 test_06 test_07 test_08 test_09 test_10 test_11 test_12 test_13 test_14 test_15 test_16 test_17 test_18 test_19 test_20 test_21 test_22 test_23 test_24 test_25 test_26 test_27 test_28 test_29 test_30
Score / Max Score 160 / 50000 162 / 50000 155 / 50000 161 / 50000 171 / 50000 157 / 50000 156 / 50000 156 / 50000 147 / 50000 153 / 50000 159 / 50000 156 / 50000 151 / 50000 163 / 50000 146 / 50000 163 / 50000 147 / 50000 148 / 50000 150 / 50000 151 / 50000 159 / 50000 155 / 50000 155 / 50000 142 / 50000 148 / 50000 155 / 50000 154 / 50000 138 / 50000 147 / 50000 146 / 50000
Status
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
Set Name Test Cases
test_01 subtask_01_01.txt
test_02 subtask_01_02.txt
test_03 subtask_01_03.txt
test_04 subtask_01_04.txt
test_05 subtask_01_05.txt
test_06 subtask_01_06.txt
test_07 subtask_01_07.txt
test_08 subtask_01_08.txt
test_09 subtask_01_09.txt
test_10 subtask_01_10.txt
test_11 subtask_01_11.txt
test_12 subtask_01_12.txt
test_13 subtask_01_13.txt
test_14 subtask_01_14.txt
test_15 subtask_01_15.txt
test_16 subtask_01_16.txt
test_17 subtask_01_17.txt
test_18 subtask_01_18.txt
test_19 subtask_01_19.txt
test_20 subtask_01_20.txt
test_21 subtask_01_21.txt
test_22 subtask_01_22.txt
test_23 subtask_01_23.txt
test_24 subtask_01_24.txt
test_25 subtask_01_25.txt
test_26 subtask_01_26.txt
test_27 subtask_01_27.txt
test_28 subtask_01_28.txt
test_29 subtask_01_29.txt
test_30 subtask_01_30.txt
Case Name Status Exec Time Memory
subtask_01_01.txt AC 2579 ms 4840 KB
subtask_01_02.txt AC 2687 ms 3316 KB
subtask_01_03.txt AC 2206 ms 3316 KB
subtask_01_04.txt AC 2033 ms 3316 KB
subtask_01_05.txt AC 2231 ms 3316 KB
subtask_01_06.txt AC 2580 ms 3316 KB
subtask_01_07.txt AC 2361 ms 3316 KB
subtask_01_08.txt AC 2262 ms 3316 KB
subtask_01_09.txt AC 2614 ms 3316 KB
subtask_01_10.txt AC 2243 ms 3316 KB
subtask_01_11.txt AC 2442 ms 3316 KB
subtask_01_12.txt AC 2375 ms 3316 KB
subtask_01_13.txt AC 2683 ms 3316 KB
subtask_01_14.txt AC 2271 ms 3316 KB
subtask_01_15.txt AC 2363 ms 3316 KB
subtask_01_16.txt AC 2877 ms 3316 KB
subtask_01_17.txt AC 2119 ms 3316 KB
subtask_01_18.txt AC 2131 ms 3316 KB
subtask_01_19.txt AC 2306 ms 3316 KB
subtask_01_20.txt AC 2135 ms 3316 KB
subtask_01_21.txt AC 2447 ms 3316 KB
subtask_01_22.txt AC 2717 ms 3316 KB
subtask_01_23.txt AC 2630 ms 3316 KB
subtask_01_24.txt AC 2044 ms 3316 KB
subtask_01_25.txt AC 2437 ms 3316 KB
subtask_01_26.txt AC 2984 ms 3348 KB
subtask_01_27.txt AC 2315 ms 3316 KB
subtask_01_28.txt AC 2637 ms 3316 KB
subtask_01_29.txt AC 2437 ms 3316 KB
subtask_01_30.txt AC 1930 ms 3316 KB