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