Submission #1176942


Source Code Expand

import sys
import time
from random import random

H, W, K, T = 30, 30, 450, 10000
p = 0.6

dx = (1, 0, -1, 0,)
dy = (0, 1, 0, -1,)
drc = ['R', 'D', 'L', 'U']

def solve():
    start = time.time()

    # Input
    input()
    s, g = [], []

    for i in range(K):
        a, b, c, d = map(int, input().split())
        s.append([a - 1, b - 1])
        g.append((c - 1, d - 1))

    # Process
    L, res = tekito(s, g, start)

    # Output
    print(L)
    print(*res, sep='\n')

def tekito(s, g, start):
    res = []

    ban = [[0]*W for i in range(H)]
    ban_next = [[0]*W for i in range(H)]

    for i in range(K):
        a, b = s[i]
        ban[a][b] = 1

    for lp in range(T):
        cmd = ''
        for i in range(K):
            a, b = s[i]
            c, d = g[i]

            if a > c:
                if ban[a - 1][b] == 0 and ban_next[a - 1][b] == 0:
                    cmd += 'U'
                    ban_next[a - 1][b] = 1
                    s[i][0] -= 1
                    continue
            if a < c:
                if ban[a + 1][b] == 0 and ban_next[a + 1][b] == 0:
                    cmd += 'D'
                    ban_next[a + 1][b] = 1
                    s[i][0] += 1
                    continue
            if b > d:
                if ban[a][b - 1] == 0 and ban_next[a][b - 1] == 0:
                    cmd += 'L'
                    ban_next[a][b - 1] = 1
                    s[i][1] -= 1
                    continue
            if b < d:
                if ban[a][b + 1] == 0 and ban_next[a][b + 1] == 0:
                    cmd += 'R'
                    ban_next[a][b + 1] = 1
                    s[i][1] += 1
                    continue

            if random() < p:
                for j in range(len(dx)):
                    if not(0 <= a + dy[j] < H):
                        continue
                    if not(0 <= b + dx[j] < W):
                        continue
                    if ban[a + dy[j]][b + dx[j]] == 0 and ban_next[a + dy[j]][b + dx[j]] == 0:
                        cmd += drc[j]
                        ban_next[a + dy[j]][b + dx[j]] = 1
                        s[i][0] += dy[j]
                        s[i][1] += dx[j]
                        break
                else:
                    cmd += '-'
                    ban_next[a][b] = 1
            else:
                cmd += '-'
                ban_next[a][b] = 1

        if cmd == '-'*K or lp >= 3000:
            break
        else:
            res.append(cmd)

            for i in range(H):
                ban[i] = ban_next[i][:]

            for i in range(H):
                ban_next[i] = [0] * W

    return len(res), res

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

if __name__ == '__main__':
    solve()

Submission Info

Submission Time
Task B - 日本橋大渋滞
User nanae
Language Python (3.4.3)
Score 8421
Code Size 2978 Byte
Status AC
Exec Time 2014 ms
Memory 6904 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 309 / 50000 328 / 50000 327 / 50000 333 / 50000 304 / 50000 343 / 50000 274 / 50000 375 / 50000 276 / 50000 308 / 50000 178 / 50000 301 / 50000 232 / 50000 273 / 50000 305 / 50000 279 / 50000 261 / 50000 251 / 50000 116 / 50000 373 / 50000 217 / 50000 309 / 50000 142 / 50000 179 / 50000 292 / 50000 283 / 50000 328 / 50000 317 / 50000 259 / 50000 349 / 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 1871 ms 6904 KB
subtask_01_02.txt AC 1733 ms 6396 KB
subtask_01_03.txt AC 1799 ms 6396 KB
subtask_01_04.txt AC 1858 ms 6396 KB
subtask_01_05.txt AC 1802 ms 6396 KB
subtask_01_06.txt AC 1788 ms 6396 KB
subtask_01_07.txt AC 1811 ms 6396 KB
subtask_01_08.txt AC 1778 ms 6396 KB
subtask_01_09.txt AC 1812 ms 6396 KB
subtask_01_10.txt AC 1825 ms 6396 KB
subtask_01_11.txt AC 1871 ms 6396 KB
subtask_01_12.txt AC 1881 ms 6396 KB
subtask_01_13.txt AC 1837 ms 6396 KB
subtask_01_14.txt AC 1890 ms 6396 KB
subtask_01_15.txt AC 1774 ms 6396 KB
subtask_01_16.txt AC 1817 ms 6396 KB
subtask_01_17.txt AC 1886 ms 6396 KB
subtask_01_18.txt AC 1900 ms 6396 KB
subtask_01_19.txt AC 2014 ms 6396 KB
subtask_01_20.txt AC 1882 ms 6396 KB
subtask_01_21.txt AC 1848 ms 6396 KB
subtask_01_22.txt AC 1760 ms 6396 KB
subtask_01_23.txt AC 1918 ms 6396 KB
subtask_01_24.txt AC 1863 ms 6396 KB
subtask_01_25.txt AC 1798 ms 6396 KB
subtask_01_26.txt AC 1870 ms 6396 KB
subtask_01_27.txt AC 1830 ms 6396 KB
subtask_01_28.txt AC 1802 ms 6396 KB
subtask_01_29.txt AC 1835 ms 6396 KB
subtask_01_30.txt AC 1806 ms 6396 KB