RCO presents 日本橋ハーフマラソン 予選

Submission #1151278

Source codeソースコード

import java.util.*;

public class Main {
    private static final int[] DR = {1, 0, -1, 0};
    private static final int[] DC = {0, 1, 0, -1};
    static Scanner sc = new Scanner(System.in);
    static SplittableRandom rnd = new SplittableRandom();
    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);

        for (int i = 0; i < H; i++) {
            Arrays.fill(used[i], false);
        }
        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);
                for (int j = 0; j < K; j++) {
                    used[p.y[j]][p.x[j]] = true;
                }
            }
        }
        System.out.println(usedPieces.size());
        for (Piece piece : usedPieces) {
            for (int i = 0; i < K; i++) {
                System.out.println((piece.y[i] + 1) + " " + (piece.x[i] + 1));
            }
        }
    }

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

Submission

Task問題 A - Multiple Pieces
User nameユーザ名 tomerun
Created time投稿日時
Language言語 Java8 (OpenJDK 1.8.0)
Status状態 AC
Score得点 945243
Source lengthソースコード長 4013 Byte
File nameファイル名
Exec time実行時間 5349 ms
Memory usageメモリ使用量 619372 KB

Test case

Set

Set name Score得点 / Max score Cases
test_01 95792 / 1343058 subtask_01_01.txt
test_02 90027 / 1343058 subtask_01_02.txt
test_03 96749 / 1343058 subtask_01_03.txt
test_04 90016 / 1343058 subtask_01_04.txt
test_05 101624 / 1343058 subtask_01_05.txt
test_06 91625 / 1343058 subtask_01_06.txt
test_07 97948 / 1343058 subtask_01_07.txt
test_08 87304 / 1343058 subtask_01_08.txt
test_09 98471 / 1343058 subtask_01_09.txt
test_10 95687 / 1343058 subtask_01_10.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
subtask_01_01.txt AC 3503 ms 513376 KB
subtask_01_02.txt AC 3663 ms 551628 KB
subtask_01_03.txt AC 3734 ms 561464 KB
subtask_01_04.txt AC 4960 ms 615644 KB
subtask_01_05.txt AC 5349 ms 610436 KB
subtask_01_06.txt AC 4884 ms 586792 KB
subtask_01_07.txt AC 3899 ms 567700 KB
subtask_01_08.txt AC 3620 ms 527328 KB
subtask_01_09.txt AC 4914 ms 619372 KB
subtask_01_10.txt AC 4705 ms 603676 KB