Submission #1175194
Source Code Expand
# 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(0):
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)
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
if g is not None:
if y0 < y1:
dds = [1] + ds
elif y0 > y1:
dds = [0] + ds
else:
dds = [2] + ds
else:
if y0 < y1:
dds = [1] + ds
elif y0 > y1:
dds = [0] + ds
else:
dds = ds
random.shuffle(dds)
for d in dds:
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 < lmi+3 and nx < x0:
continue
if X + rmi-3 < nx-1 and x0 < nx:
continue
else:
if not g[1] - 1 < ny < g[1] + 1:
if nx-1 < lmi+2 and nx < x0:
continue
if X + rmi-2 < nx-1 and x0 < nx:
continue
else:
if nx-1 < lidx[y1] and nx < x0:
continue
if X + ridx[ny] < nx-1 and x0 < nx:
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 Info
Submission Time |
|
Task |
B - 日本橋大渋滞 |
User |
yaketake08 |
Language |
Python (2.7.6) |
Score |
749062 |
Code Size |
5391 Byte |
Status |
AC |
Exec Time |
2857 ms |
Memory |
5864 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 |
26151 / 50000 |
24667 / 50000 |
25880 / 50000 |
26206 / 50000 |
24343 / 50000 |
26681 / 50000 |
24379 / 50000 |
25524 / 50000 |
24167 / 50000 |
25291 / 50000 |
25734 / 50000 |
25330 / 50000 |
25189 / 50000 |
25407 / 50000 |
25189 / 50000 |
25694 / 50000 |
25485 / 50000 |
23332 / 50000 |
24320 / 50000 |
24655 / 50000 |
22584 / 50000 |
24583 / 50000 |
25721 / 50000 |
23993 / 50000 |
24864 / 50000 |
24343 / 50000 |
25681 / 50000 |
23202 / 50000 |
24667 / 50000 |
25800 / 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 |
2390 ms |
5864 KB |
subtask_01_02.txt |
AC |
2306 ms |
4724 KB |
subtask_01_03.txt |
AC |
2389 ms |
4468 KB |
subtask_01_04.txt |
AC |
2235 ms |
4468 KB |
subtask_01_05.txt |
AC |
2417 ms |
4724 KB |
subtask_01_06.txt |
AC |
2197 ms |
4468 KB |
subtask_01_07.txt |
AC |
2425 ms |
4724 KB |
subtask_01_08.txt |
AC |
2293 ms |
4596 KB |
subtask_01_09.txt |
AC |
2653 ms |
4724 KB |
subtask_01_10.txt |
AC |
2492 ms |
4596 KB |
subtask_01_11.txt |
AC |
2376 ms |
4468 KB |
subtask_01_12.txt |
AC |
2388 ms |
4596 KB |
subtask_01_13.txt |
AC |
2390 ms |
4596 KB |
subtask_01_14.txt |
AC |
2344 ms |
4596 KB |
subtask_01_15.txt |
AC |
2594 ms |
4596 KB |
subtask_01_16.txt |
AC |
2268 ms |
4596 KB |
subtask_01_17.txt |
AC |
2454 ms |
4596 KB |
subtask_01_18.txt |
AC |
2668 ms |
4852 KB |
subtask_01_19.txt |
AC |
2727 ms |
4724 KB |
subtask_01_20.txt |
AC |
2586 ms |
4596 KB |
subtask_01_21.txt |
AC |
2857 ms |
4980 KB |
subtask_01_22.txt |
AC |
2499 ms |
4596 KB |
subtask_01_23.txt |
AC |
2406 ms |
4596 KB |
subtask_01_24.txt |
AC |
2780 ms |
4724 KB |
subtask_01_25.txt |
AC |
2464 ms |
4596 KB |
subtask_01_26.txt |
AC |
2601 ms |
4724 KB |
subtask_01_27.txt |
AC |
2266 ms |
4596 KB |
subtask_01_28.txt |
AC |
2814 ms |
4852 KB |
subtask_01_29.txt |
AC |
2542 ms |
4596 KB |
subtask_01_30.txt |
AC |
2340 ms |
4596 KB |