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 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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 |