Submission #1151175


Source Code Expand

import java.util.*;

public class Main {
    private static final long TL = 9800;
    private static final boolean DEBUG = false;
    private static final int[] DR = {1, 0, -1, 0};
    private static final int[] DC = {0, 1, 0, -1};
    static final long startTime = System.currentTimeMillis();
    static Scanner sc = new Scanner(System.in);
    static XorShift rnd = new XorShift();
    static long[][] hash;
    static int H, W, K;
    static int[][] f;
    static boolean[][] used;
    static ArrayList<Piece> pieces = new ArrayList<>();
    static ArrayList<HashSet<Long>> usedHashes = new ArrayList<>();

    public static void main(String[] args) {
        H = sc.nextInt();
        W = sc.nextInt();
        K = sc.nextInt();
        f = new int[H][W];
        used = new boolean[H][W];
        hash = new long[H][W];
        for (int i = 0; i < H; i++) {
            String row = sc.next();
            for (int j = 0; j < W; j++) {
                f[i][j] = row.charAt(j) - '0';
                hash[i][j] = ((long) rnd.nextInt() << 32) | rnd.nextInt();
                if (f[i][j] == 0) used[i][j] = true;
            }
        }
        for (int i = 0; i <= K; i++) {
            usedHashes.add(new HashSet<>());
        }
        enumerate();
        System.err.println(pieces.size());
        Collections.sort(pieces);
//        State bestState = beamSearch(pieces);
//        ArrayList<Piece> ans = bestState.ps;
//        System.err.println(bestState.score);

        ArrayList<Piece> ans = null;
        long bestScore = 0;
        long worstInterval = 0;
        for (int turn = 0; turn < 1; turn++) {
            long elapsed = System.currentTimeMillis() - startTime;
            if (elapsed > TL - worstInterval) {
                break;
            }
            for (int i = 0; i < H; i++) {
                Arrays.fill(used[i], false);
            }
            long score = 0;
            ArrayList<Piece> usedPieces = new ArrayList<>((int) (0.85 * H * W / K));
            for (int i = pieces.size() - 1; i >= 0; i--) {
                boolean ok = true;
                Piece p = pieces.get(i);
                for (int j = 0; j < K; j++) {
                    if (used[p.y[j]][p.x[j]]) {
                        ok = false;
                        break;
                    }
                }
                if (ok) {
                    usedPieces.add(p);
                    score += p.score;
                    for (int j = 0; j < K; j++) {
                        used[p.y[j]][p.x[j]] = true;
                    }
                }
            }
//            System.err.println("score:" + score);
            if (score > bestScore) {
                ans = usedPieces;
                bestScore = score;
            }
            for (int i = 0; i < pieces.size() / 30; i++) {
                int p = rnd.nextInt(pieces.size());
                int p2 = p + rnd.nextInt(65) - 32;
                if (p2 < 0) p2 = 0;
                if (p2 >= pieces.size()) p2 = pieces.size() - 1;
                Piece tmp = pieces.get(p);
                pieces.set(p, pieces.get(p2));
                pieces.set(p2, tmp);
            }
            worstInterval = Math.max(worstInterval, System.currentTimeMillis() - startTime - elapsed);
        }
        System.out.println(ans.size());
        for (Piece piece : ans) {
//            System.err.println(piece.score);
            for (int i = 0; i < K; i++) {
                System.out.println((piece.y[i] + 1) + " " + (piece.x[i] + 1));
            }
        }
    }

    static State beamSearch(ArrayList<Piece> pieces) {
        final int L = 5;
        State[][] states = new State[(int) (0.9 * H * W / K)][L];
        states[0][0] = new State();
        State best = states[0][0];
        int maxUse = 0;
        for (int i = pieces.size() - 1; i >= 0; i--) {
//            if (i % 1000 == 0) System.err.println(i);
            if ((i & 0x3F) == 0 && System.currentTimeMillis() - startTime > TL) {
                for (int j = i; j >= 0; j--) {
                    if (best.canUse(pieces.get(j))) best.add(pieces.get(j));
                }
                break;
            }
            Piece p = pieces.get(i);
            for (int j = maxUse; j >= 0; j--) {
                if (p.score * (H * W * 0.9 / K - j) + states[j][0].score <= best.score) {
                    break;
                }
                for (int k = 0; k < L; k++) {
                    State st = states[j][k];
                    if (st == null) break;
                    if (!st.canUse(p)) continue;
                    long nextScore = st.score + p.score;
                    State[] nStates = states[j + 1];
                    if (nStates[L - 1] != null && nextScore <= nStates[L - 1].score) {
                        break;
                    }
                    int insertPos = 0;
                    for (int l = 0; l < L; l++) {
                        if (nStates[l] == null) {
                            insertPos = l;
                            break;
                        } else if (nextScore > nStates[l].score) {
                            insertPos = l;
                            break;
                        }
                    }
                    for (int l = L - 1; l > insertPos; l--) {
                        nStates[l] = nStates[l - 1];
                    }
                    nStates[insertPos] = new State(st, p);
                    if (j == maxUse) maxUse++;
                    if (nStates[insertPos].score > best.score) best = nStates[insertPos];
                }
            }
        }
        return best;
    }

    static void enumerate() {
        int[] x = new int[K];
        int[] y = new int[K];
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                x[0] = j;
                y[0] = i;
                if (f[i][j] == 0) continue;
                used[i][j] = true;
                for (int k = 1; k <= K; k++) {
                    usedHashes.get(k).clear();
                }
                dfs(x, y, hash[i][j], f[i][j], 1);
            }
        }
    }

    static void dfs(int[] x, int[] y, long h, int score, int depth) {
        for (int i = 0; i < depth; i++) {
            for (int j = 0; j < 4; j++) {
                int nr = y[i] + DR[j];
                int nc = x[i] + DC[j];
                if (nr < 0 || H <= nr || nc < 0 || W <= nc) continue;
                if (used[nr][nc]) continue;
                long nextHash = h ^ hash[nr][nc];
                if (usedHashes.get(depth).contains(nextHash)) continue;
                usedHashes.get(depth).add(nextHash);
                x[depth] = nc;
                y[depth] = nr;
                if (depth == K - 1) {
                    pieces.add(new Piece(x, y, score * f[nr][nc]));
                    continue;
                }
                used[nr][nc] = true;
                dfs(x, y, nextHash, score * f[nr][nc], depth + 1);
                used[nr][nc] = false;
            }
        }
    }

    static class State {
        ArrayList<Piece> ps;
        long score;
        long[] used;

        State() {
            this.ps = new ArrayList<>();
            this.used = new long[H];
        }

        State(State prev, Piece p) {
            this.ps = new ArrayList<>(prev.ps);
            this.ps.add(p);
            this.score = prev.score + p.score;
            this.used = prev.used.clone();
            for (int i = 0; i < K; i++) {
                this.used[p.y[i]] |= (1L << p.x[i]);
            }
        }

        boolean canUse(Piece p) {
            for (int i = 0; i < K; i++) {
                if ((this.used[p.y[i]] & (1L << p.x[i])) != 0) return false;
            }
            return true;
        }

        void add(Piece p) {
            this.ps.add(p);
            this.score += p.score;
            for (int i = 0; i < K; i++) {
                this.used[p.y[i]] |= (1L << p.x[i]);
            }
        }
    }

    static class Piece implements Comparable<Piece> {
        int[] x, y;
        int score;

        public Piece(int[] x, int[] y, int score) {
            this.x = x.clone();
            this.y = y.clone();
            this.score = score;
        }

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

    static final class XorShift {
        int x = 123456789;
        int y = 362436069;
        int z = 521288629;
        int w = 88675123;
        static final double TO_DOUBLE = 1.0 / (1L << 31);

        int nextInt(int n) {
            final int t = x ^ (x << 11);
            x = y;
            y = z;
            z = w;
            w = (w ^ (w >>> 19)) ^ (t ^ (t >>> 8));
            final int r = w % n;
            return r < 0 ? r + n : r;
        }

        int nextInt() {
            final int t = x ^ (x << 11);
            x = y;
            y = z;
            z = w;
            w = (w ^ (w >>> 19)) ^ (t ^ (t >>> 8));
            return w;
        }

        boolean nextBoolean() {
            final int t = x ^ (x << 11);
            x = y;
            y = z;
            z = w;
            w = (w ^ (w >>> 19)) ^ (t ^ (t >>> 8));
            return (w & 8) == 0;
        }

        double nextDouble() {
            final int t = x ^ (x << 11);
            x = y;
            y = z;
            z = w;
            w = (w ^ (w >>> 19)) ^ (t ^ (t >>> 8));
            return Math.abs(w * TO_DOUBLE);
        }

        double nextSDouble() {
            final int t = x ^ (x << 11);
            x = y;
            y = z;
            z = w;
            w = (w ^ (w >>> 19)) ^ (t ^ (t >>> 8));
            return w * TO_DOUBLE;
        }
    }
}

Submission Info

Submission Time
Task A - Multiple Pieces
User tomerun
Language Java8 (OpenJDK 1.8.0)
Score 945243
Code Size 10013 Byte
Status AC
Exec Time 4954 ms
Memory 614620 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
Score / Max Score 95792 / 1343058 90027 / 1343058 96749 / 1343058 90016 / 1343058 101624 / 1343058 91625 / 1343058 97948 / 1343058 87304 / 1343058 98471 / 1343058 95687 / 1343058
Status
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
Case Name Status Exec Time Memory
subtask_01_01.txt AC 3411 ms 511140 KB
subtask_01_02.txt AC 3803 ms 554764 KB
subtask_01_03.txt AC 3763 ms 564792 KB
subtask_01_04.txt AC 4954 ms 614620 KB
subtask_01_05.txt AC 4952 ms 612132 KB
subtask_01_06.txt AC 3547 ms 517632 KB
subtask_01_07.txt AC 4686 ms 590092 KB
subtask_01_08.txt AC 3699 ms 565816 KB
subtask_01_09.txt AC 4867 ms 612668 KB
subtask_01_10.txt AC 3461 ms 508400 KB