#860192 (Java21) No.5015 Escape from Labyrinth

提出ソース

結果

問題	No.5015 Escape from Labyrinth
ユーザー	Yu_212
提出日時	2023-04-16 14:03:18
言語	Java21 (openjdk 21)
結果	WA
実行時間	-
コード長	17,610 bytes
コンパイル時間	6,707 ms
コンパイル使用メモリ	94,892 KB
実行使用メモリ	71,292 KB
スコア	41,530
最終ジャッジ日時	2023-04-16 14:04:38
合計ジャッジ時間	75,550 ms
ジャッジサーバーID （参考情報）	judge15 / judge12

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	607 ms 68,548 KB
testcase_01	AC	656 ms 70,424 KB
testcase_02	AC	601 ms 67,852 KB
testcase_03	AC	620 ms 68,640 KB
testcase_04	AC	655 ms 67,048 KB
testcase_05	AC	642 ms 68,368 KB
testcase_06	AC	596 ms 68,992 KB
testcase_07	AC	608 ms 67,520 KB
testcase_08	AC	576 ms 64,900 KB
testcase_09	AC	587 ms 68,628 KB
testcase_10	AC	597 ms 66,712 KB
testcase_11	AC	594 ms 68,796 KB
testcase_12	AC	637 ms 67,408 KB
testcase_13	AC	590 ms 68,480 KB
testcase_14	AC	631 ms 68,720 KB
testcase_15	AC	591 ms 68,628 KB
testcase_16	AC	613 ms 68,652 KB
testcase_17	AC	626 ms 69,128 KB
testcase_18	AC	580 ms 66,896 KB
testcase_19	AC	580 ms 68,760 KB
testcase_20	AC	636 ms 66,924 KB
testcase_21	AC	607 ms 68,404 KB
testcase_22	AC	610 ms 68,224 KB
testcase_23	AC	593 ms 69,224 KB
testcase_24	AC	610 ms 69,076 KB
testcase_25	AC	591 ms 69,068 KB
testcase_26	AC	587 ms 68,988 KB
testcase_27	AC	626 ms 68,500 KB
testcase_28	AC	584 ms 67,308 KB
testcase_29	AC	585 ms 67,016 KB
testcase_30	AC	573 ms 64,448 KB
testcase_31	AC	693 ms 68,672 KB
testcase_32	AC	622 ms 68,580 KB
testcase_33	AC	606 ms 68,868 KB
testcase_34	AC	691 ms 68,596 KB
testcase_35	AC	685 ms 69,132 KB
testcase_36	AC	617 ms 66,860 KB
testcase_37	AC	609 ms 68,676 KB
testcase_38	AC	603 ms 68,496 KB
testcase_39	AC	619 ms 68,292 KB
testcase_40	AC	572 ms 66,528 KB
testcase_41	AC	595 ms 68,360 KB
testcase_42	AC	583 ms 66,460 KB
testcase_43	AC	594 ms 64,888 KB
testcase_44	AC	704 ms 68,960 KB
testcase_45	AC	605 ms 68,884 KB
testcase_46	AC	617 ms 65,624 KB
testcase_47	AC	571 ms 67,024 KB
testcase_48	AC	713 ms 69,668 KB
testcase_49	AC	660 ms 68,980 KB
testcase_50	AC	680 ms 68,716 KB
testcase_51	AC	619 ms 68,612 KB
testcase_52	AC	675 ms 69,260 KB
testcase_53	AC	647 ms 68,956 KB
testcase_54	AC	649 ms 68,904 KB
testcase_55	AC	656 ms 68,644 KB
testcase_56	AC	670 ms 68,652 KB
testcase_57	AC	645 ms 68,904 KB
testcase_58	AC	590 ms 68,912 KB
testcase_59	AC	629 ms 69,436 KB
testcase_60	AC	640 ms 67,428 KB
testcase_61	AC	569 ms 67,104 KB
testcase_62	AC	625 ms 67,444 KB
testcase_63	AC	668 ms 68,672 KB
testcase_64	AC	626 ms 69,180 KB
testcase_65	AC	598 ms 67,388 KB
testcase_66	AC	680 ms 69,280 KB
testcase_67	AC	574 ms 62,504 KB
testcase_68	AC	587 ms 67,368 KB
testcase_69	AC	642 ms 64,792 KB
testcase_70	AC	593 ms 66,804 KB
testcase_71	AC	616 ms 67,152 KB
testcase_72	AC	637 ms 69,072 KB
testcase_73	AC	574 ms 66,468 KB
testcase_74	AC	621 ms 69,060 KB
testcase_75	AC	698 ms 69,016 KB
testcase_76	AC	660 ms 69,172 KB
testcase_77	AC	593 ms 66,496 KB
testcase_78	AC	624 ms 68,904 KB
testcase_79	AC	583 ms 67,276 KB
testcase_80	AC	622 ms 68,568 KB
testcase_81	AC	625 ms 69,516 KB
testcase_82	AC	600 ms 66,536 KB
testcase_83	AC	573 ms 69,080 KB
testcase_84	AC	623 ms 67,444 KB
testcase_85	AC	646 ms 69,016 KB
testcase_86	AC	577 ms 66,548 KB
testcase_87	AC	626 ms 67,068 KB
testcase_88	AC	577 ms 64,900 KB
testcase_89	AC	603 ms 69,052 KB
testcase_90	AC	595 ms 68,216 KB
testcase_91	AC	604 ms 68,232 KB
testcase_92	WA	-
testcase_93	AC	635 ms 67,372 KB
testcase_94	AC	653 ms 66,748 KB
testcase_95	AC	635 ms 68,752 KB
testcase_96	AC	625 ms 68,720 KB
testcase_97	AC	664 ms 67,252 KB
testcase_98	AC	669 ms 68,780 KB
testcase_99	AC	648 ms 69,016 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

import java.io.*;
import java.util.*;
import java.util.concurrent.ThreadLocalRandom;
import java.util.function.IntUnaryOperator;
import java.util.function.LongUnaryOperator;
import java.util.stream.Collectors;

public class Main {
    static boolean isLocal;
    Random rand = new Random();
    In in = new In(System.in);
    PrintStream out = System.out;
    long inf = 0x1fffffffffffffffL;
    int iinf = 0x3fffffff;
    long startTime;

    public static final int N = 60;
    public int D;
    public static final int H = 1500;
    public int M;
    public int J;
    public char[] grid;
    public Pos[] ps;
    public int[] ds;
    public Pos[] jps;
    int[] distances;
    int[][] route;
    boolean[][] beam = new boolean[60][N * N];
    int[] avgWait = new int[N * N];
    int[] jid = new int[N * N];
    public static final String[] ss = {"M L", "M U", "M R", "M D", "S"};
    long solve(int seed) {
        startTime = System.currentTimeMillis();
        in();
        distances = new int[(J+3) * (J+3)];
        route = new int[(J+3) * (J+3)][];
        Arrays.fill(distances, iinf);
        for (int i = 0; i < M; i++) {
            for (int d = 0; d < 4; d++) {
                Pos cur = ps[i];
                while (true) {
                    cur = cur.moved((d+2)%4);
                    if (cur == null || grid[cur.z] == '#') {
                        break;
                    }
                    for (int j = 0; j < 60; j += ds[i]) {
                        beam[j][cur.z] = true;
                    }
                }
            }
        }
        for (int i = 0; i < N * N; i++) {
            int c = 1;
            for (int j = 0; j < 60; j++) {
                if (beam[j][i]) {
                    c++;
                } else {
                    c = 1;
                }
                avgWait[i] += c;
            }
        }
        for (int i = 0; i < J + 3; i++) {
            calcDist(i);
        }
        int tt = 0;
        int cur = J;
        BitSet visited = new BitSet(J + 3);
        visited.set(J + 2);
        tt = moveTo(J, J+1, tt, visited);
        visited.clear(J + 2);
        tt = moveTo(J+1, J+2, tt, visited);
        debug(totalCost);
        return 0;
    }

    int totalCost = 0;
    int moveTo(int s, int g, int tt, BitSet visited) {
        int cur = s;
        visited.set(s);
        while (cur != g) {
            int md = iinf;
            int mi = -1;
            for (int i = 0; i < J + 3; i++) {
                if (visited.get(i)) {
                    continue;
                }
//                debug(i, cur, jps[i].dist(jps[g]), distances[cur * (J + 3) + i]);
                int d = distances[cur * (J + 3) + i] + jps[i].dist(jps[g]) * 50;
                if (md > d) {
                    md = d;
                    mi = i;
                }
            }
            visited.set(mi);
//            debug(cur, mi, md, distances[cur * (J + 3) + mi], jps[mi].dist(jps[g]), g);
            Pos p = jps[cur];
            for (int v : route(jps[cur], jps[mi], tt)) {
                if (v < 4) p = p.moved(v);
                tt = (tt + 1) % 60;
                if (beam[tt][p.z]) {
                    totalCost += D;
                }
                totalCost++;
                out.println(ss[v]);
            }
            cur = mi;
        }
        return tt;
    }

    List<Integer> route(Pos s, Pos g, int tt) {
        class S {
            private final Pos p;
            private final int t;
            private final int d;

            public S(Pos p, int t, int d) {
                this.p = p;
                this.t = t;
                this.d = d;
            }
        }
        PriorityQueue<S> queue = new PriorityQueue<>(Comparator.comparingInt(v -> v.d));
        queue.add(new S(s, tt, 0));
        int[][] dist = new int[60][N * N];
        int[][] prev = new int[60][N * N];
        for (int i = 0; i < 60; i++) {
            Arrays.fill(dist[i], iinf);
            Arrays.fill(prev[i], -1);
        }
        dist[tt][s.z] = 0;
        while (!queue.isEmpty()) {
            S v = queue.remove();
            if (dist[v.t][v.p.z] < v.d) {
                continue;
            }
            if (v.p.z == g.z) {
                List<Integer> route = new ArrayList<>();
                Pos cur = v.p;
                int ct = v.t;
                while (prev[ct][cur.z] != -1) {
                    route.add(prev[ct][cur.z]);
                    if (prev[ct][cur.z] < 4) {
                        cur = cur.moved((prev[ct][cur.z] + 2) % 4);
                    }
                    ct = (ct + 59) % 60;
                }
                Collections.reverse(route);
                return route;
            }
            int nt = (v.t + 1) % 60;
            for (int d = 0; d < 4; d++) {
                Pos q = v.p.moved(d);
                if (q == null || grid[q.z] == '#') {
                    continue;
                }
                int cost = dist[v.t][v.p.z] + 1 + (beam[nt][q.z] ? D : 0);
                if (dist[nt][q.z] > cost) {
                    dist[nt][q.z] = cost;
                    prev[nt][q.z] = d;
                    queue.add(new S(q, nt, cost));
                }
            }
            int cost = dist[v.t][v.p.z] + 1 + (beam[nt][v.p.z] ? D : 0);
            if (dist[nt][v.p.z] > cost) {
                dist[nt][v.p.z] = cost;
                prev[nt][v.p.z] = 4;
                queue.add(new S(v.p, nt, cost));
            }
        }
        throw new RuntimeException();
    }

//    void calcDist(int s, int t) {
//        Deque<Timing> deque = new ArrayDeque<>();
//        deque.add(new Timing(ps[s], t));
//        int[] dist = new int[N * N];
//        int[] prev = new int[N * N];
//        Timing[] prevState = new Timing[N * N];
//        Arrays.fill(dist, iinf);
//        dist[ps[s].z] = 0;
//        distances[t][s * (M+3) + s] = 0;
//        route[t][s * (M+3) + s] = new int[0];
//        while (!deque.isEmpty()) {
//            Timing p = deque.removeFirst();
//            if (mid[p.p.z] != -1 && mid[p.p.z] != s) {
//                distances[t][s * (M+3) + mid[p.p.z]] = dist[p.p.z];
//                route[t][s * (M+3) + mid[p.p.z]] = new int[dist[p.p.z]];
//                int j = dist[p.p.z];
//                Timing cur = p;
//                while (j > 0) {
//                    j--;
//                    route[t][s * (M+3) + mid[p.p.z]][j] = prev[cur.p.z];
//                    cur = prevState[cur.p.z];
//                }
//            }
//            int nt = (p.t + 1) % 60;
//            for (int d = 0; d < 4; d++) {
//                Pos q = p.p.moved(d);
//                if (q == null || grid[q.z] == '#' || grid[q.z] == 'E') {
//                    continue;
//                }
//                if (beam[q.z][nt]) {
//                    continue;
//                }
//                int cost = beam[nt][q.z] ? D : 1;
//                if (dist[q.z] > dist[p.p.z] + 1 && q.dist(ps[s]) < iinf) {
//                    dist[q.z] = dist[p.p.z] + 1;
//                    prev[q.z] = d;
//                    prevState[q.z] = p;
//                    deque.addLast(new Timing(q, nt));
//                }
//            }
//            if (dist[p.p.z] > dist[p.p.z] + 1) {
//                dist[p.p.z] = dist[p.p.z] + 1;
//                prev[p.p.z] = 5;
//                prevState[p.p.z] = p;
//                deque.addLast(new Timing(p.p, nt));
//            }
//        }
//    }

    void calcDist(int s) {
        class S {
            private final Pos p;
            private final int d;

            public S(Pos p, int d) {
                this.p = p;
                this.d = d;
            }
        }
        PriorityQueue<S> queue = new PriorityQueue<>(Comparator.comparingInt(v -> v.d));
        queue.add(new S(jps[s], 0));
        int[] dist = new int[N * N];
        Arrays.fill(dist, iinf);
        dist[jps[s].z] = 0;
        while (!queue.isEmpty()) {
            S v = queue.remove();
            if (dist[v.p.z] < v.d) {
                continue;
            }
            if (jid[v.p.z] != -1) {
                distances[s * (J+3) + jid[v.p.z]] = v.d;
            }
            for (int d = 0; d < 4; d++) {
                Pos q = v.p.moved(d);
                if (q == null || grid[q.z] == '#') {
                    continue;
                }
                int cost = dist[v.p.z] + avgWait[q.z];
                if (dist[q.z] > cost && q.dist(jps[s]) < iinf) {
                    dist[q.z] = cost;
                    queue.add(new S(q, cost));
                }
            }
        }
    }

    void in() {
        in.nextInt();
        D = in.nextInt();
        in.nextInt();
        grid = new char[N * N];
        int jc = 0;
        for (int i = 0; i < N; i++) {
            char[] s = in.nextCharArray();
            for (int j = 0; j < N; j++) {
                grid[i * N + j] = s[j];
                if (grid[i * N + j] == 'J') {
                    jc++;
                }
            }
        }
        M = in.nextInt();
        J = jc;
        jps = new Pos[J + 3];
        ps = new Pos[M];
        ds = new int[M];
        for (int i = 0; i < M; i++) {
            int y = in.nextInt();
            int x = in.nextInt();
            int d = in.nextInt();
            ps[i] = pos(x, y);
            ds[i] = d;
        }
        jc = 0;
        Arrays.fill(jid, -1);
        for (int i = 0; i < N * N; i++) {
            if (grid[i] == 'S') {
                jps[J] = pos(i);
                jid[i] = J;
                grid[i] = '.';
            } else if (grid[i] == 'K') {
                jps[J + 1] = pos(i);
                jid[i] = J + 1;
                grid[i] = '.';
            } else if (grid[i] == 'G') {
                jps[J + 2] = pos(i);
                jid[i] = J + 2;
                grid[i] = '.';
            } else if (grid[i] == 'J') {
                jid[i] = jc;
                jps[jc++] = pos(i);
            } else if (grid[i] == 'E') {
                grid[i] = '#';
            }
        }
    }

    static Pos pos(int x, int y) {
        return Pos.instances[y * N + x];
    }

    static Pos pos(int z) {
        return Pos.instances[z];
    }

    static class Timing {
        Pos p;
        int t, z;

        public Timing(Pos p, int t) {
            this.p = p;
            this.t = t;
            this.z = p.z * 60 + t;
        }
    }

    static class Pos implements Comparable<Pos> {
        static Pos[] instances;
        static Pos[] moved;
        static {
            instances = new Pos[N * N];
            moved = new Pos[4 * N * N];
            for (int i = 0; i < N * N; i++) {
                instances[i] = new Pos(i % N, i / N, i);
            }
            for (int i = 0; i < N * N; i++) {
                for (int d = 0; d < 4; d++) { // LURD
                    int nx = i % N + (d - 1) % 2;
                    int ny = i / N + (d - 2) % 2;
                    if (0 <= nx && nx < N && 0 <= ny && ny < N) {
                        moved[i * 4 + d] = instances[ny * N + nx];
                    }
                }
            }
        }

        final int x, y, z;

        private Pos(int x, int y, int z) {
            this.x = x;
            this.y = y;
            this.z = z;
        }

        Pos moved(int d) {
            return moved[z * 4 + d];
        }

        int dist(Pos o) {
            return Math.abs(x - o.x) + Math.abs(y - o.y);
        }

        Pos[] neighbors() {
            Pos[] p = new Pos[4];
            int i = 0;
            if ((p[i] = moved(0)) != null) i++;
            if ((p[i] = moved(1)) != null) i++;
            if ((p[i] = moved(2)) != null) i++;
            if ((p[i] = moved(3)) != null) i++;
            return i == 4 ? p : Arrays.copyOf(p, i);
        }

        @Override
        public int compareTo(Pos o) {
            return Integer.compare(z, o.z);
        }

        @Override
        public boolean equals(Object o) {
            return o instanceof Pos && z == ((Pos)o).z;
        }

        @Override
        public int hashCode() {
            return z;
        }

        @Override
        public String toString() {
            return String.format("(%d, %d)", x, y);
        }
    }

    static void debug(Object... args) {
        if (!isLocal) {
            return;
        }
        if (args == null || args.getClass() != Object[].class) {
            args = new Object[] {args};
        }
        System.err.println(Arrays.stream(args).map(obj -> {
            Class<?> clazz = obj == null ? null : obj.getClass();
            return clazz == byte[].class ? Arrays.toString((byte[])obj) :
                   clazz == short[].class ? Arrays.toString((short[])obj) :
                   clazz == int[].class ? Arrays.toString((int[])obj) :
                   clazz == long[].class ? Arrays.toString((long[])obj) :
                   clazz == char[].class ? Arrays.toString((char[])obj) :
                   clazz == float[].class ? Arrays.toString((float[])obj) :
                   clazz == double[].class ? Arrays.toString((double[])obj) :
                   clazz == boolean[].class ? Arrays.toString((boolean[])obj) :
                   obj instanceof Object[] ? Arrays.deepToString((Object[])obj) :
                   String.valueOf(obj);
        }).collect(Collectors.joining(" ")));
    }

    long elapsed() {
        return (long)((System.currentTimeMillis() - startTime) * (isLocal ? 1.7 : 1));
    }

    boolean elapsed(long timeLimit) {
        return elapsed() >= timeLimit;
    }

    public static void main(String[] args) {
        new Main().solve(0);
    }

    static class Random {
        private long x, y, z, w;

        Random() {
            this(ThreadLocalRandom.current().nextLong());
        }

        Random(long seed) {
            this.x = seed;
            for (int i = 0; i < 20; i++) {
                rand();
            }
        }

        private long rand() {
            long t = x ^ (x << 11);
            x = y;
            y = z;
            z = w;
            w = w ^ (w >>> 19) ^ t ^ (t >>> 8);
            return x & 0x7fffffff;
        }

        long next() {
            return rand() << 31 | rand();
        }

        int next(int n) {
            return (int)(rand() % n);
        }

        int next(int l, int r) {
            return (int)(rand() % (r - l) + l);
        }

        double nextDouble() {
            return rand() / 2147483647.0;
        }
    }

    static class In {
        private final BufferedReader reader;
        private StringTokenizer tokenizer;

        In(InputStream input) {
            this.reader = new BufferedReader(new InputStreamReader(input), 0x10000);
        }

        String next() {
            try {
                while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                    tokenizer = new StringTokenizer(reader.readLine());
                }
            } catch (IOException ignored) {
            }
            return tokenizer.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        char[] nextCharArray() {
            return next().toCharArray();
        }

        String[] nextStringArray(int n) {
            String[] s = new String[n];
            for (int i = 0; i < n; i++) {
                s[i] = next();
            }
            return s;
        }

        char[][] nextCharGrid(int n, int m) {
            char[][] a = new char[n][m];
            for (int i = 0; i < n; i++) {
                a[i] = next().toCharArray();
            }
            return a;
        }

        int[] nextIntArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = nextInt();
            }
            return a;
        }

        int[] nextIntArray(int n, IntUnaryOperator op) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = op.applyAsInt(nextInt());
            }
            return a;
        }

        int[][] nextIntMatrix(int h, int w) {
            int[][] a = new int[h][w];
            for (int i = 0; i < h; i++) {
                a[i] = nextIntArray(w);
            }
            return a;
        }

        long[] nextLongArray(int n) {
            long[] a = new long[n];
            for (int i = 0; i < n; i++) {
                a[i] = nextLong();
            }
            return a;
        }

        long[] nextLongArray(int n, LongUnaryOperator op) {
            long[] a = new long[n];
            for (int i = 0; i < n; i++) {
                a[i] = op.applyAsLong(nextLong());
            }
            return a;
        }

        long[][] nextLongMatrix(int h, int w) {
            long[][] a = new long[h][w];
            for (int i = 0; i < h; i++) {
                a[i] = nextLongArray(w);
            }
            return a;
        }

        List<List<Integer>> nextEdges(int n, int m, boolean directed) {
            List<List<Integer>> res = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                res.add(new ArrayList<>());
            }
            for (int i = 0; i < m; i++) {
                int u = nextInt() - 1;
                int v = nextInt() - 1;
                res.get(u).add(v);
                if (!directed) {
                    res.get(v).add(u);
                }
            }
            return res;
        }
    }
}

yukicoder

結果

テストケース

ソースコード