結果

問題 No.5016 Worst Mayor
ユーザー Yu_212Yu_212
提出日時 2023-04-29 15:18:54
言語 Java21
(openjdk 21)
結果
RE  
実行時間 -
コード長 23,971 bytes
コンパイル時間 4,046 ms
コンパイル使用メモリ 104,980 KB
実行使用メモリ 87,496 KB
スコア 17,168,442,530
平均クエリ数 353.40
最終ジャッジ日時 2023-04-29 15:20:01
合計ジャッジ時間 65,319 ms
ジャッジサーバーID
(参考情報)
judge13 / judge15
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,184 ms
85,996 KB
testcase_01 RE -
testcase_02 AC 1,077 ms
85,332 KB
testcase_03 AC 1,210 ms
84,548 KB
testcase_04 RE -
testcase_05 AC 1,102 ms
83,276 KB
testcase_06 AC 1,093 ms
85,172 KB
testcase_07 AC 1,083 ms
86,164 KB
testcase_08 RE -
testcase_09 AC 1,273 ms
85,220 KB
testcase_10 AC 1,060 ms
83,248 KB
testcase_11 AC 1,052 ms
84,480 KB
testcase_12 AC 1,032 ms
85,892 KB
testcase_13 AC 1,138 ms
86,004 KB
testcase_14 AC 1,089 ms
85,416 KB
testcase_15 AC 1,133 ms
85,568 KB
testcase_16 AC 1,113 ms
86,824 KB
testcase_17 AC 1,077 ms
84,964 KB
testcase_18 AC 1,114 ms
84,440 KB
testcase_19 AC 1,317 ms
86,312 KB
testcase_20 AC 1,082 ms
85,756 KB
testcase_21 RE -
testcase_22 AC 1,060 ms
85,488 KB
testcase_23 AC 1,115 ms
85,932 KB
testcase_24 AC 1,138 ms
85,944 KB
testcase_25 AC 1,035 ms
83,436 KB
testcase_26 AC 1,078 ms
85,156 KB
testcase_27 AC 1,086 ms
84,300 KB
testcase_28 RE -
testcase_29 RE -
testcase_30 RE -
testcase_31 AC 1,019 ms
85,052 KB
testcase_32 AC 1,110 ms
85,204 KB
testcase_33 AC 1,113 ms
85,432 KB
testcase_34 AC 1,078 ms
85,684 KB
testcase_35 AC 1,132 ms
83,316 KB
testcase_36 AC 1,137 ms
84,964 KB
testcase_37 RE -
testcase_38 AC 1,040 ms
84,740 KB
testcase_39 AC 1,064 ms
86,400 KB
testcase_40 AC 1,202 ms
85,300 KB
testcase_41 AC 1,053 ms
86,012 KB
testcase_42 AC 1,054 ms
84,240 KB
testcase_43 AC 1,122 ms
84,216 KB
testcase_44 AC 1,052 ms
84,832 KB
testcase_45 AC 1,118 ms
85,136 KB
testcase_46 AC 1,053 ms
85,348 KB
testcase_47 RE -
testcase_48 AC 1,129 ms
85,144 KB
testcase_49 AC 1,145 ms
85,300 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

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 long[] TABLE = new long[364];
    public static final int[] COST = {0,10000000,7071067,5773502,5000000,4472135,4082482,3779644,3535533,3333333,3162277,3015113,2886751,2773500,2672612,2581988,2500000,2425356,2357022,2294157,2236067,2182178,2132007,2085144,2041241,2000000,1961161,1924500,1889822,1856953,1825741,1796053,1767766,1740776,1714985,1690308,1666666,1643989,1622214,1601281,1581138,1561737,1543033,1524985,1507556,1490711,1474419,1458649,1443375,1428571,1414213,1400280,1386750,1373605,1360827,1348399,1336306,1324532,1313064,1301889,1290994,1280368,1270001,1259881,1250000,1240347,1230914,1221694,1212678,1203858,1195228,1186781,1178511,1170411,1162476,1154700,1147078,1139605,1132277,1125087,1118033,1111111,1104315,1097642,1091089,1084652,1078327,1072112,1066003,1059997,1054092,1048284,1042572,1036951,1031421,1025978,1020620,1015346,1010152,1005037,1000000,995037,990147,985329,980580,975900,971285,966736,962250,957826,953462,949157,944911,940720,936585,932504,928476,924500,920574,916698,912870,909090,905357,901669,898026,894427,890870,887356,883883,880450,877058,873704,870388,867109,863868,860662,857492,854357,851256,848188,845154,842151,839181,836242,833333,830454,827605,824786,821994,819231,816496,813788,811107,808452,805822,803219,800640,798086,795557,793051,790569,788110,785674,783260,780868,778498,776150,773823,771516,769230,766964,764719,762492,760285,758098,755928,753778,751646,749531,747435,745355,743294,741249,739221,737209,735214,733235,731272,729324,727392,725476,723574,721687,719815,717958,716114,714285,712470,710669,708881,707106,705345,703597,701862,700140,698430,696733,695048,693375,691714,690065,688428,686802,685188,683585,681994,680413,678844,677285,675737,674199,672672,671156,669649,668153,666666,665190,663723,662266,660818,659380,657951,656532,655121,653720,652328,650944,649569,648203,646846,645497,644156,642824,641500,640184,638876,637576,636284,635000,633724,632455,631194,629940,628694,627455,626224,625000,623782,622572,621369,620173,618984,617802,616626,615457,614295,613139,611990,610847,609710,608580,607456,606339,605227,604122,603022,601929,600841,599760,598684,597614,596549,595491,594438,593390,592348,591312,590281,589255,588235,587220,586210,585205,584206,583211,582222,581238,580258,579284,578314,577350,576390,575435,574484,573539,572598,571661,570730,569802,568880,567961,567047,566138,565233,564332,563436,562543,561655,560772,559892,559016,558145,557278,556414,555555,554700,553848,553001,552157,551317,550481,549649,548821,547996,547175,546358,545544,544734,543928,543125,542326,541530,540738,539949,539163,538381,537603,536828,536056,535287,534522,533760,533001,532246,531494,530744,529998,529256,528516,527779,527046,526315,525588,524863,524142,523423,522708,521995,521286,520579,519875,519174,518475,517780,517087,516397,515710,515026,514344,513665,512989,512315,511644,510976,510310,509647,508986,508328,507673,507020,506369,505721,505076,504433,503792,503154,502518,501885,501254,500626,500000};
    public static final int S = 14;
    public static final int SS = 196;
    public static final int N = 3000;
    public static final int T = 400;
    long solve(int seed) {
        startTime = System.currentTimeMillis();
        Arrays.setAll(TABLE, i -> rand.next());
        in();
        Trace trace = new Trace();
        State2 result = greedy(new State2(), trace);
//        State2 result = beamSearch(new State2(), trace, 10, 2000);
        debug(result.score);
        int turn = 0;
        int money = 1000000;
        for (int i = 0; i < 49; i++) {
            ask2();
            turn++;
        }

        int k = 0;
        int lastU = 0;
        for (Action action : trace.trace(result.id)) {
            while (money < COST[50]) {
                ask3();
                turn++;
                money += 50000 + 60 * lastU;
            }
            debug(k++, pos(action.x), action.v, action.opened.score);
            ask1(action.x, action.v);
            lastU = action.opened.score;
            money += 60 * lastU - COST[50];
            turn++;
        }
        while (turn < T) {
            ask3();
            turn++;
        }
        return isLocal ? 0 : 0;
    }

    void ask1(int x, boolean v) {
        if (!isLocal) {
            in.nextInt();
            in.nextInt();
        }
        Pos px = pos(x);
        Pos py = pos(x + (v ? S : 1));
        out.println("1 " + (px.x+1) + " " + (px.y+1) + " " + (py.x+1) + " " + (py.y+1));
        out.flush();
    }

    void ask2() {
        if (!isLocal) {
            in.nextInt();
            in.nextInt();
        }
        out.println(2);
        out.flush();
    }

    void ask3() {
        if (!isLocal) {
            in.nextInt();
            in.nextInt();
        }
        out.println(3);
        out.flush();
    }

    Pos[] fs, ts;
    void in() {
        Pos.init(S);
        in.nextInt();
        in.nextInt();
        fs = new Pos[N];
        ts = new Pos[N];
        for (int i = 0; i < N; i++) {
            int a = in.nextInt() - 1;
            int b = in.nextInt() - 1;
            int c = in.nextInt() - 1;
            int d = in.nextInt() - 1;
            fs[i] = pos(a, b);
            ts[i] = pos(c, d);
        }
    }

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

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

    static class Pos implements Comparable<Pos> {
        static Pos[] instances = new Pos[SS];
        static Pos[] moved = new Pos[4 * SS];
        static void init(int 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);
        }
    }

//    class State {
//        int collabo;
//        int money;
//        BitSet vert;
//        BitSet hori;
//
//        int constructCost() {
//            return COST[collabo];
//        }
//    }

    State2 initialState() {
        return new State2();
    }

    class State2 implements Comparable<State2> {
        int id;
        State2 prev;
        int score;
        long hash;
        BitSet vert; // |
        BitSet hori; // -
        int[] dist;
        int[] uses;

        State2() {
            this.id = -1;
            this.hash = 0;
            this.vert = new BitSet(182);
            this.hori = new BitSet(182);
            this.dist = new int[N];
            this.uses = new int[N];
            for (int i = 0; i < N; i++) {
                dist[i] = Math.abs(fs[i].x - ts[i].x) + Math.abs(fs[i].y - ts[i].y);
            }
        }

        State2(State2 prev) {
            this.id = prev.id;
            this.prev = prev;
            this.score = prev.score;
            this.hash = prev.hash;
            this.vert = (BitSet)prev.vert.clone();
            this.hori = (BitSet)prev.hori.clone();
            this.dist = prev.dist.clone();
            this.uses = prev.uses.clone();
        }

        boolean highway(Pos p, int d) {
            if ((d & 1) == 0) { // LURD
                return hori.get(p.z - (d>>1^1));
            } else {
                return vert.get(p.z - (d>>1^1) * S);
            }
        }

        int dist(int d, int u) {
            return d * 1000 - u * 777;
        }

        void update(int x, boolean v) {
            int y = x + (v ? S : 1);
            (v ? vert : hori).set(x);
            hash ^= TABLE[x + (v ? 182 : 0)];
            Deque<Pos> deque1 = new ArrayDeque<>();
            Deque<Pos> deque2 = new ArrayDeque<>();
            BitSet fromY = new BitSet(SS);
            deque1.add(pos(x));
            deque1.add(pos(y));
            deque2.add(pos(x));
            deque2.add(pos(y));
            fromY.set(y);
            int[] ds = new int[SS];
            int[] us = new int[SS];
            Arrays.fill(ds, 30);
            ds[x] = 0;
            ds[y] = 0;
            while (!deque1.isEmpty() || !deque2.isEmpty()) {
                Pos p1 = deque1.isEmpty() ? null : deque1.peekFirst();
                Pos p2 = deque2.isEmpty() ? null : deque2.peekFirst();
                Pos p;
                boolean h = p2 == null || p1 != null && dist(ds[p1.z], us[p1.z]) < dist(ds[p2.z], us[p2.z]);
                if (h) {
                    p = deque1.removeFirst();
                } else {
                    p = deque2.removeFirst();
                }
                for (int i = 0; i < 4; i++) {
                    Pos q = p.moved(i);
                    if (q == null || highway(p, i) != h) {
                        continue;
                    }
                    int nd = ds[p.z] + 1;
                    int nu = us[p.z] + (h ? 1 : 0);
                    if (dist(ds[q.z], us[q.z]) > dist(nd, nu)) {
                        ds[q.z] = nd;
                        us[q.z] = nu;
                        fromY.set(q.z, fromY.get(p.z));
                        deque1.addLast(q);
                        deque2.addLast(q);
                    }
                }
            }
            for (int i = 0; i < N; i++) {
                if (fromY.get(fs[i].z) == fromY.get(ts[i].z)) {
                    continue;
                }
                int nd = ds[fs[i].z] + ds[ts[i].z] + 1;
                int nu = us[fs[i].z] + us[ts[i].z] + 1;
                if (dist(dist[i], uses[i]) > dist(nd, nu)) {
                    score += nu - uses[i];
                    dist[i] = nd;
                    uses[i] = nu;
                }
            }
        }

        boolean finished(int turn) {
            return turn == 50;
        }

        static int[] ord = new int[182];
        static {
            Arrays.setAll(ord, i -> i);
        }
        List<Action> actions() {
            List<Action> nexts = new ArrayList<>();
            for (int ii = 0; ii < 50; ii++) {
                int j = ii + rand.next(182 - ii);
                int i = ord[j];
                ord[j] = ord[ii];
                ord[ii] = i;
                if (!vert.get(i)) {
                    nexts.add(new Action(this, hash ^ TABLE[i + 182], i, true));
                }
                if (!hori.get(i)) {
                    nexts.add(new Action(this, hash ^ TABLE[i], i, false));
                }
            }
            return nexts;
        }

        void advance(Trace trace, Action action) {
            hash = action.hash;
            score = action.score;
            id = trace.add(action, id);
        }

        State2 copy() {
            return new State2(this);
        }

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

    class Action implements Comparable<Action> {
        State2 prev;
        State2 opened;
        long hash;
        int score;
        int x;
        boolean v;

        Action(State2 prev, long hash, int x, boolean v) {
            this.prev = prev;
            this.hash = hash;
            this.x = x;
            this.v = v;
        }

        void open() {
            opened = prev.copy();
            opened.update(x, v);
            score = opened.score;
        }

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

    static class Trace {
        List<Action> log = new ArrayList<>();
        List<Integer> prev = new ArrayList<>();

        int add(Action action, int pi) {
            log.add(action);
            prev.add(pi);
            return log.size() - 1;
        }

        List<Action> trace(int id) {
            List<Action> actions = new ArrayList<>();
            while (id != -1) {
                actions.add(log.get(id));
                id = prev.get(id);
            }
            Collections.reverse(actions);
            return actions;
        }

        Action first(int id) {
            Action first = null;
            while (id != -1) {
                first = log.get(id);
                id = prev.get(id);
            }
            return first;
        }

        void clear() {
            log.clear();
            prev.clear();
        }
    }

    State2 beamSearch(State2 initialState, Trace trace, int beamWidth, long timeLimit) {
        long[] hashes = new long[1 << 20];
        initialState.id = -1;
        State2[] beam = {initialState};
        State2 best = null;
        for (int turn = 1; ; turn++) {
            boolean sorted = false;
            int numCand = 0;
            Action[] cand = new Action[beamWidth * 2];
            for (State2 state : beam) {
                if (state == null) {
                    break;
                }
                for (Action action : state.actions()) {
                    int key = (int)(action.hash & 0xfffff);
                    if (hashes[key] != action.hash) {
                        hashes[key] = action.hash;
                        action.open();
                        if (sorted && cand[beamWidth - 1].score > action.score) {
                            continue;
                        }
                        cand[numCand++] = action;
                        if (numCand == cand.length) {
                            Arrays.sort(cand, Comparator.reverseOrder());
                            numCand = beamWidth;
                            sorted = true;
                        }
                    }
                }
            }
            Arrays.sort(cand);
            int size = Math.min(beamWidth, numCand);
            State2[] next = new State2[size];
            int j = 0;
            State2 found = null;
            for (int i = 0; i < numCand && j < size; i++) {
                Action action = cand[i];
                State2 copy = action.opened;
                copy.advance(trace, action);
                if (best == null || best.score < copy.score) {
                    best = copy;
                }
                if (copy.finished(turn)) {
                    if (found == null || found.score < copy.score) {
                        found = copy;
                    }
                    continue;
                }
                next[j++] = copy;
            }
            if (found != null) {
                return found;
            }
            if (j == 0 || elapsed(timeLimit)) {
                throw new RuntimeException();
            }
            beam = next;
        }
    }

    State2 greedy(State2 state, Trace trace) {
        state.id = -1;
        for (int turn = 1; ; turn++) {
            Action best = null;
            for (Action next : state.actions()) {
                next.open();
                if (best == null || best.score < next.score) {
                    best = next;
                }
            }
            state = best.opened;
            state.advance(trace, best);
            if (state.finished(turn)) {
                return state;
            }
        }
    }

    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 BinarySearchTree<E extends Comparable<E>> implements Iterable<E> {
        private final int n;
        private final Object[] a;
        private int size;

        public BinarySearchTree(int n) {
            this.n = n;
            this.a = new Object[n];
        }

        public int size() {
            return size;
        }

        public void add(E element) {
            if (size < n) {
                int i = size++;
                while (i > 0) {
                    int parent = (i - 1) / 2;
                    if (get(parent).compareTo(element) <= 0) {
                        break;
                    }
                    a[i] = a[parent];
                    i = parent;
                }
                a[i] = element;
            } else if (n > 0 && get(0).compareTo(element) < 0) {
                int i = 0;
                while (i * 2 + 1 < n) {
                    int child = i * 2 + 1;
                    if (child + 1 < n && get(child).compareTo(get(child + 1)) > 0) {
                        child++;
                    }
                    if (get(child).compareTo(element) >= 0) {
                        break;
                    }
                    a[i] = a[child];
                    i = child;
                }
                a[i] = element;
            }
        }

        @SuppressWarnings("unchecked")
        private E get(int index) {
            return (E)a[index];
        }

        @Override
        public Iterator<E> iterator() {
            return new Iterator<E>() {
                private int i = 0;

                @Override
                public boolean hasNext() {
                    return i < size;
                }

                @Override
                public E next() {
                    return get(i++);
                }
            };
        }
    }

    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;
        }
    }
}
0