Submission #1174379


Source Code Expand

import java.util.ArrayList;
import java.util.Scanner;
import java.util.SplittableRandom;
 
public class Main {
 
    static long startTime = System.currentTimeMillis();
    static final int TL = 3990;
    static final int[] DR = new int[]{1, 0, -1, 0, 0};
    static final int[] DC = new int[]{0, 1, 0, -1, 0};
    static final char[] DIR_CHARS = "DRUL-".toCharArray();
    static Scanner sc = new Scanner(System.in);
    static SplittableRandom rnd = new SplittableRandom(42);
    static int H, W, K, T;
    static int[][] carPos, origCarPos, convergePos;
    static char[][] moves;
    static int[] order;
    static int time;
    static int sumDist;
    static int[][] used;
    static int usedIdx;
 
    public static void main(String[] args) {
        H = sc.nextInt();
        W = sc.nextInt();
        K = sc.nextInt();
        T = sc.nextInt();
        carPos = new int[4][K];
        origCarPos = new int[4][K];
        convergePos = new int[4][K];
        order = new int[K];
        for (int i = 0; i < K; i++) {
            for (int j = 0; j < 4; j++) {
                origCarPos[j][i] = sc.nextInt() - 1;
            }
            order[i] = i;
        }
        moves = new char[T][K];
        used = new int[H][W];
        ArrayList<String> ans = new ArrayList<>();
        double ansScore = 0;
 
        long worstTime = 0;
        for (int turn = 0; ; turn++) {
            long beforeTime = System.currentTimeMillis() - startTime;
            if (beforeTime + worstTime > TL) {
                System.err.println("turn:" + turn);
                break;
            }
            for (int i = 0; i < 4; i++) {
                System.arraycopy(origCarPos[i], 0, carPos[i], 0, K);
            }
            sumDist = 0;
            for (int i = 0; i < K; i++) {
                sumDist += Math.abs(carPos[0][i] - carPos[2][i]) + Math.abs(carPos[1][i] - carPos[3][i]);
            }
 
            int bestTime = 0;
            double bestScore = calcScore(sumDist, 0);
            for (time = 1; time <= T; time++) {
                boolean update = move();
                if (!update) break;
                double score = calcScore(sumDist, time);
                if (score > bestScore) {
                    bestScore = score;
                    bestTime = time;
                }
                if (calcScore(0, time) < ansScore) {
                    System.err.println("time:" + time);
                    break;
                }
            }
            System.err.println("bestScore:" + bestScore);
            if (bestScore > ansScore) {
                ansScore = bestScore;
                ans.clear();
                for (int i = 0; i < bestTime; i++) {
                    ans.add(String.valueOf(moves[i]));
                }
            }
 
            worstTime = Math.max(worstTime, System.currentTimeMillis() - startTime - beforeTime);
        }
        System.out.println(ans.size());
        for (String s : ans) {
            System.out.println(s);
        }
    }
 
    static boolean move() {
        usedIdx++;
        for (int i = 0; i < K; i++) {
            int pos = rnd.nextInt(K - i) + i;
            int tmp = order[i];
            order[i] = order[pos];
            order[pos] = tmp;
            used[carPos[0][i]][carPos[1][i]] = usedIdx;
        }
        ArrayList<Integer> nearList = new ArrayList<>();
        ArrayList<Integer> farList = new ArrayList<>();
        int stayFactor;
        if (sumDist < 100) {
            stayFactor = 99;
        } else if (sumDist < 200) {
            stayFactor = 4;
        } else if (sumDist < 300) {
            stayFactor = 2;
        } else if (sumDist < 500) {
            stayFactor = 2;
        } else if (sumDist < 1000) {
            stayFactor = 1;
        } else {
            stayFactor = 0;
        }
 
        sumDist = 0;
        boolean update = false;
        for (int i = 0; i < K; i++) {
            nearList.clear();
            farList.clear();
            int ci = order[i];
            int dist = Math.abs(carPos[1][ci] - carPos[3][ci]) + Math.abs(carPos[0][ci] - carPos[2][ci]);
            for (int j = 0; j < 4; j++) {
                int nr = carPos[0][ci] + DR[j];
                int nc = carPos[1][ci] + DC[j];
                if (nr < 0 || H <= nr || nc < 0 || W <= nc) continue;
                if (used[nr][nc] == usedIdx) continue;
                int nDist = Math.abs(nr - carPos[2][ci]) + Math.abs(nc - carPos[3][ci]);
                if (dist > nDist) {
                    nearList.add(j);
                } else {
                    farList.add(j);
                }
            }
            int dir;
            if (dist == 0 && stayFactor == 99) {
                dir = 4;
            } else if (nearList.size() == 1) {
                dir = nearList.get(0);
                --dist;
            } else if (nearList.size() == 2) {
                int nr0 = carPos[0][ci] + DR[nearList.get(0)];
                int nc0 = carPos[1][ci] + DC[nearList.get(0)];
                int distFromEdge0 = distFromEdge(nr0, nc0);
                int nr1 = carPos[0][ci] + DR[nearList.get(1)];
                int nc1 = carPos[1][ci] + DC[nearList.get(1)];
                int distFromEdge1 = distFromEdge(nr1, nc1);
                if (distFromEdge0 < distFromEdge1) {
                    nearList.add(nearList.get(0));
                } else if (distFromEdge0 > distFromEdge1) {
                    nearList.add(nearList.get(1));
                }
                dir = nearList.get(rnd.nextInt(nearList.size()));
                --dist;
            } else if (!farList.isEmpty()) {
                if (stayFactor == 0 && farList.size() >= 2) {
                    int nr0 = carPos[0][ci] + DR[farList.get(0)];
                    int nc0 = carPos[1][ci] + DC[farList.get(0)];
                    int distFromEdge0 = distFromEdge(nr0, nc0);
                    int nr1 = carPos[0][ci] + DR[farList.get(1)];
                    int nc1 = carPos[1][ci] + DC[farList.get(1)];
                    int distFromEdge1 = distFromEdge(nr1, nc1);
                    if (distFromEdge0 < distFromEdge1) {
                        farList.add(farList.get(0));
                    } else if (distFromEdge0 > distFromEdge1) {
                        farList.add(farList.get(1));
                    }
                }
                for (int j = 0; j < stayFactor; j++) {
                    farList.add(4);
                }
                dir = farList.get(rnd.nextInt(farList.size()));
                if (dir != 4) dist++;
            } else {
                dir = 4;
            }
            moves[time - 1][ci] = DIR_CHARS[dir];
            carPos[0][ci] += DR[dir];
            carPos[1][ci] += DC[dir];
            used[carPos[0][ci]][carPos[1][ci]] = usedIdx;
            sumDist += dist;
            if (dir != 4) update = true;
        }
        return update;
    }
 
    static int distFromEdge(int r, int c) {
        return Math.min(Math.min(r, H - 1 - r), Math.min(c, W - 1 - c));
    }
 
    static double calcScore(int dist, int time) {
        double distFactor = 20 + dist;
        double timeFactor = 10 + 0.01 * time;
        return 10_000_000.0 / (distFactor * timeFactor);
    }
}

Submission Info

Submission Time
Task B - 日本橋大渋滞
User tomerun
Language Java8 (OpenJDK 1.8.0)
Score 800461
Code Size 7414 Byte
Status AC
Exec Time 3891 ms
Memory 60120 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 29326 / 50000 30322 / 50000 29121 / 50000 27825 / 50000 25044 / 50000 26667 / 50000 23497 / 50000 29482 / 50000 24202 / 50000 24962 / 50000 26897 / 50000 25240 / 50000 25051 / 50000 26169 / 50000 24571 / 50000 27825 / 50000 25988 / 50000 27145 / 50000 24814 / 50000 25721 / 50000 28043 / 50000 28297 / 50000 27732 / 50000 24438 / 50000 25760 / 50000 29586 / 50000 26414 / 50000 25563 / 50000 25155 / 50000 29604 / 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 3714 ms 57060 KB
subtask_01_02.txt AC 3878 ms 55436 KB
subtask_01_03.txt AC 3712 ms 55296 KB
subtask_01_04.txt AC 3661 ms 54000 KB
subtask_01_05.txt AC 3723 ms 58112 KB
subtask_01_06.txt AC 3780 ms 55472 KB
subtask_01_07.txt AC 3765 ms 54656 KB
subtask_01_08.txt AC 3758 ms 57388 KB
subtask_01_09.txt AC 3769 ms 55956 KB
subtask_01_10.txt AC 3820 ms 57796 KB
subtask_01_11.txt AC 3677 ms 55332 KB
subtask_01_12.txt AC 3428 ms 54780 KB
subtask_01_13.txt AC 3538 ms 55536 KB
subtask_01_14.txt AC 3821 ms 57332 KB
subtask_01_15.txt AC 3672 ms 53312 KB
subtask_01_16.txt AC 3886 ms 55884 KB
subtask_01_17.txt AC 3813 ms 53200 KB
subtask_01_18.txt AC 3826 ms 54904 KB
subtask_01_19.txt AC 3793 ms 57436 KB
subtask_01_20.txt AC 3777 ms 58364 KB
subtask_01_21.txt AC 3799 ms 57824 KB
subtask_01_22.txt AC 3891 ms 52980 KB
subtask_01_23.txt AC 3828 ms 55840 KB
subtask_01_24.txt AC 3861 ms 57952 KB
subtask_01_25.txt AC 3757 ms 57684 KB
subtask_01_26.txt AC 3745 ms 60120 KB
subtask_01_27.txt AC 3849 ms 57560 KB
subtask_01_28.txt AC 3792 ms 56756 KB
subtask_01_29.txt AC 3853 ms 55532 KB
subtask_01_30.txt AC 3865 ms 55832 KB