Submission #1174388
Source Code Expand
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time
sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7
def LI(): return list(map(int, input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return input()
def main():
h,w,k,t = LI()
a = []
b = []
for _ in range(k):
c,d,e,f = LI()
b.append([c-1,d-1])
a.append([e-1,f-1])
def ds(a, b):
return abs(a[0]-b[0]) + abs(a[1]-b[1])
co = (h//2, w//2)
ma = []
for i in range(h):
for j in range(w):
if (i+j) % 2 == 0:
ma.append((i,j))
def mp(a, m):
b = [[False]*w for _ in range(h)]
nt = []
for i in range(k):
ai = a[i]
b[ai[0]][ai[1]] = i+1
if (ai[0]+ai[1]) % 2 == 1:
nt.append(ai)
nt.sort()
for i in range(k):
mi = m[i]
if b[mi[0]][mi[1]]:
continue
s = list(mi)
t = nt[0]
nt = nt[1:]
while s[0] != t[0] or s[1] != t[1]:
sn = list(s)
while True:
if sn[0] > t[0]:
sn[0] -= 1
elif sn[0] < t[0]:
sn[0] += 1
elif sn[1] < t[1]:
sn[1] += 1
elif sn[1] > t[1]:
sn[1] -= 1
if b[sn[0]][sn[1]]:
break
b[s[0]][s[1]] = b[sn[0]][sn[1]]
b[sn[0]][sn[1]] = False
s = sn
r = [None] * k
for i in range(h):
for j in range(w):
if b[i][j]:
r[b[i][j]-1] = (i,j)
return r
def move(a, tr):
for i in range(k):
c = tr[i]
if c == 'U':
a[i][0] -= 1
elif c == 'D':
a[i][0] += 1
elif c == 'L':
a[i][1] -= 1
elif c == 'R':
a[i][1] += 1
def mp_move(b, ma):
rr = []
while True:
mb = mp(b, ma)
tr = ['-'] * k
f = [[True]*w for _ in range(h)]
for bi in b:
f[bi[0]][bi[1]] = False
mc = 0
for i in range(k):
bi = b[i]
mi = mb[i]
if bi[0] > mi[0]:
if f[bi[0]-1][bi[1]]:
tr[i] = 'U'
f[bi[0]-1][bi[1]] = False
continue
elif bi[0] < mi[0]:
if f[bi[0]+1][bi[1]]:
tr[i] = 'D'
f[bi[0]+1][bi[1]] = False
continue
if bi[1] > mi[1]:
if f[bi[0]][bi[1]-1]:
tr[i] = 'L'
f[bi[0]][bi[1]-1] = False
continue
elif bi[1] < mi[1]:
if f[bi[0]][bi[1]+1]:
tr[i] = 'R'
f[bi[0]][bi[1]+1] = False
continue
mc += 1
if mc == k:
break
move(b,tr)
rr.append(tr)
return (b, rr)
def mp_mp(b, a):
rr = []
aa = list(zip(a, range(k)))
aa.sort()
for _ in range(200):
tr = [['-'] * k for _ in range(2)]
f = [[True]*w for _ in range(h)]
mc = 0
bis = {}
for i in range(k):
bis[tuple(b[i])] = i
for ai, i in aa:
a0, a1 = ai
b0, b1 = b[i]
if b[i] == ai or not f[b0][b1]:
mc += 1
continue
if b0 > a0 and b1 > a1:
if f[b0-1][b1-1] and f[b0-1][b1] and f[b0][b1-1]:
nb = bis[(b0-1, b1-1)]
if a[nb] > a[i]:
f[b0][b1] = f[b0-1][b1-1] = f[b0-1][b1] = f[b0][b1-1] = False
tr[0][i] = 'U'
tr[1][i] = 'L'
tr[0][nb] = 'D'
tr[1][nb] = 'R'
continue
if b0 > a0 and b1 < a1:
if f[b0-1][b1+1] and f[b0-1][b1] and f[b0][b1+1]:
nb = bis[(b0-1, b1+1)]
if a[nb] > a[i]:
f[b0][b1] = f[b0-1][b1+1] = f[b0-1][b1] = f[b0][b1+1] = False
tr[0][i] = 'U'
tr[1][i] = 'R'
tr[0][nb] = 'D'
tr[1][nb] = 'L'
continue
if b0-1 > a0:
if f[b0-2][b1]:
if b1 < w-1 and f[b0][b1+1] and f[b0-2][b1+1]:
nb1 = bis[(b0-2,b1)]
nb2 = bis[(b0-1,b1+1)]
if a[nb1] > a[i] and a[nb2] > a[i]:
f[b0][b1] = f[b0-1][b1] = f[b0-2][b1] = f[b0][b1+1] = f[b0-1][b1+1] = f[b0-2][b1+1] = False
tr[0][i] = 'U'
tr[1][i] = 'U'
tr[0][nb1] = 'R'
tr[1][nb1] = 'D'
tr[0][nb2] = 'D'
tr[1][nb2] = 'L'
continue
if b1 > 0 and f[b0][b1-1] and f[b0-2][b1-1]:
nb1 = bis[(b0-2,b1)]
nb2 = bis[(b0-1,b1-1)]
if a[nb1] > a[i] and a[nb2] > a[i]:
f[b0][b1] = f[b0-1][b1] = f[b0-2][b1] = f[b0][b1-1] = f[b0-1][b1-1] = f[b0-2][b1-1] = False
tr[0][i] = 'U'
tr[1][i] = 'U'
tr[0][nb1] = 'L'
tr[1][nb1] = 'D'
tr[0][nb2] = 'D'
tr[1][nb2] = 'R'
continue
if b1-1 > a1:
if f[b0][b1-2]:
if b0 == h-1 and f[b0-1][b1] and f[b0-1][b1-2]:
nb1 = bis[(b0,b1-2)]
nb2 = bis[(b0-1,b1-1)]
f[b0][b1] = f[b0][b1-1] = f[b0][b1-2] = f[b0-1][b1] = f[b0-1][b1-1] = f[b0-1][b1-2] = False
tr[0][i] = 'L'
tr[1][i] = 'L'
tr[0][nb1] = 'U'
tr[1][nb1] = 'R'
tr[0][nb2] = 'R'
tr[1][nb2] = 'D'
continue
if b0 < h-1 and f[b0+1][b1] and f[b0+1][b1-2]:
nb1 = bis[(b0,b1-2)]
nb2 = bis[(b0+1,b1-1)]
f[b0][b1] = f[b0][b1-1] = f[b0][b1-2] = f[b0+1][b1] = f[b0+1][b1-1] = f[b0+1][b1-2] = False
tr[0][i] = 'L'
tr[1][i] = 'L'
tr[0][nb1] = 'D'
tr[1][nb1] = 'R'
tr[0][nb2] = 'R'
tr[1][nb2] = 'U'
continue
if b1+1 < a1:
if f[b0][b1+2]:
if b0 == h-1 and f[b0-1][b1] and f[b0-1][b1+2]:
nb1 = bis[(b0,b1+2)]
nb2 = bis[(b0-1,b1+1)]
f[b0][b1] = f[b0][b1+1] = f[b0][b1+2] = f[b0-1][b1] = f[b0-1][b1+1] = f[b0-1][b1+2] = False
tr[0][i] = 'R'
tr[1][i] = 'R'
tr[0][nb1] = 'U'
tr[1][nb1] = 'L'
tr[0][nb2] = 'L'
tr[1][nb2] = 'D'
continue
if b0 < h-1 and f[b0+1][b1] and f[b0+1][b1+2]:
nb1 = bis[(b0,b1+2)]
nb2 = bis[(b0+1,b1+1)]
f[b0][b1] = f[b0][b1+1] = f[b0][b1+2] = f[b0+1][b1] = f[b0+1][b1+1] = f[b0+1][b1+2] = False
tr[0][i] = 'R'
tr[1][i] = 'R'
tr[0][nb1] = 'D'
tr[1][nb1] = 'L'
tr[0][nb2] = 'L'
tr[1][nb2] = 'U'
continue
mc += 1
if mc == k:
break
move(b,tr[0])
for i in range(k):
for j in range(i+1, k):
if b[i] == b[j]:
print('error', i,j,b[i], tr[0][i], tr[0][j])
move(b,tr[1])
rr.append(tr[0])
rr.append(tr[1])
return rr
def r_rr(rr):
r = []
for tr in rr:
t = ''
for c in tr:
if c == 'U':
t += 'D'
elif c == 'D':
t += 'U'
elif c == 'L':
t += 'R'
elif c == 'R':
t += 'L'
else:
t += '-'
r.append(t)
r.reverse()
return r
b, br = mp_move(b, ma)
a, ar = mp_move(a, ma)
mr = mp_mp(b, a)
rr = br + mr + r_rr(ar)
print(len(rr))
for c in rr:
print(''.join(c))
main()
Submission Info
Submission Time |
|
Task |
B - 日本橋大渋滞 |
User |
iehn |
Language |
Python (3.4.3) |
Score |
1132004 |
Code Size |
10234 Byte |
Status |
AC |
Exec Time |
1464 ms |
Memory |
9412 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 |
37937 / 50000 |
38373 / 50000 |
37879 / 50000 |
37258 / 50000 |
38700 / 50000 |
38700 / 50000 |
38023 / 50000 |
38081 / 50000 |
37566 / 50000 |
36955 / 50000 |
36711 / 50000 |
36928 / 50000 |
37510 / 50000 |
37994 / 50000 |
36711 / 50000 |
38110 / 50000 |
37370 / 50000 |
38023 / 50000 |
37908 / 50000 |
37994 / 50000 |
37708 / 50000 |
37765 / 50000 |
37708 / 50000 |
37708 / 50000 |
37623 / 50000 |
37822 / 50000 |
37908 / 50000 |
37966 / 50000 |
36955 / 50000 |
38110 / 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 |
1327 ms |
9412 KB |
subtask_01_02.txt |
AC |
1227 ms |
6992 KB |
subtask_01_03.txt |
AC |
1291 ms |
7116 KB |
subtask_01_04.txt |
AC |
1379 ms |
7120 KB |
subtask_01_05.txt |
AC |
1193 ms |
8912 KB |
subtask_01_06.txt |
AC |
1196 ms |
6988 KB |
subtask_01_07.txt |
AC |
1277 ms |
7116 KB |
subtask_01_08.txt |
AC |
1311 ms |
7120 KB |
subtask_01_09.txt |
AC |
1350 ms |
7116 KB |
subtask_01_10.txt |
AC |
1438 ms |
7248 KB |
subtask_01_11.txt |
AC |
1464 ms |
7244 KB |
subtask_01_12.txt |
AC |
1433 ms |
7248 KB |
subtask_01_13.txt |
AC |
1352 ms |
7120 KB |
subtask_01_14.txt |
AC |
1282 ms |
7124 KB |
subtask_01_15.txt |
AC |
1462 ms |
7244 KB |
subtask_01_16.txt |
AC |
1277 ms |
6992 KB |
subtask_01_17.txt |
AC |
1375 ms |
7116 KB |
subtask_01_18.txt |
AC |
1272 ms |
7116 KB |
subtask_01_19.txt |
AC |
1285 ms |
7116 KB |
subtask_01_20.txt |
AC |
1273 ms |
7116 KB |
subtask_01_21.txt |
AC |
1327 ms |
7120 KB |
subtask_01_22.txt |
AC |
1330 ms |
7116 KB |
subtask_01_23.txt |
AC |
1353 ms |
7116 KB |
subtask_01_24.txt |
AC |
1320 ms |
7120 KB |
subtask_01_25.txt |
AC |
1317 ms |
7120 KB |
subtask_01_26.txt |
AC |
1304 ms |
7120 KB |
subtask_01_27.txt |
AC |
1301 ms |
7120 KB |
subtask_01_28.txt |
AC |
1285 ms |
7116 KB |
subtask_01_29.txt |
AC |
1426 ms |
7248 KB |
subtask_01_30.txt |
AC |
1284 ms |
6988 KB |