#678405 (Java21) No.1634 Sorting Integers (Multiple of K) Hard

提出ソース

結果

問題	No.1634 Sorting Integers (Multiple of K) Hard
ユーザー	遭難者
提出日時	2021-07-16 16:18:01
言語	Java21 (openjdk 21)
結果	TLE (最新) AC (最初)
実行時間	-
コード長	13,405 bytes
コンパイル時間	2,760 ms
コンパイル使用メモリ	88,956 KB
実行使用メモリ	92,212 KB
最終ジャッジ日時	2023-10-14 02:27:51
合計ジャッジ時間	59,917 ms
ジャッジサーバーID （参考情報）	judge12 / judge13

このコードへのチャレンジ（β）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	56 ms 50,344 KB
testcase_01	AC	56 ms 50,444 KB
testcase_02	AC	56 ms 50,628 KB
testcase_03	AC	131 ms 57,568 KB
testcase_04	AC	133 ms 57,124 KB
testcase_05	AC	1,596 ms 85,792 KB
testcase_06	AC	1,203 ms 78,932 KB
testcase_07	AC	1,820 ms 83,472 KB
testcase_08	AC	1,987 ms 91,480 KB
testcase_09	AC	57 ms 50,500 KB
testcase_10	AC	57 ms 50,344 KB
testcase_11	AC	2,062 ms 89,168 KB
testcase_12	AC	1,864 ms 89,216 KB
testcase_13	AC	2,758 ms 91,520 KB
testcase_14	TLE	-
testcase_15	AC	2,091 ms 88,608 KB
testcase_16	AC	2,693 ms 91,268 KB
testcase_17	AC	2,096 ms 92,212 KB
testcase_18	AC	1,347 ms 83,992 KB
testcase_19	AC	2,692 ms 88,588 KB
testcase_20	AC	1,028 ms 86,824 KB
testcase_21	AC	634 ms 79,036 KB
testcase_22	AC	1,868 ms 90,644 KB
testcase_23	AC	2,089 ms 89,488 KB
testcase_24	AC	1,457 ms 82,752 KB
testcase_25	AC	2,175 ms 89,216 KB
testcase_26	AC	2,152 ms 88,724 KB
testcase_27	AC	1,492 ms 83,356 KB
testcase_28	AC	1,836 ms 90,412 KB
testcase_29	AC	1,921 ms 90,348 KB
testcase_30	AC	2,656 ms 91,912 KB
testcase_31	AC	2,613 ms 91,964 KB

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

ソースコード

raw source code

import java.util.*;
import java.io.*;

class Main {
    public static void main(String[] args) {
        var sc = new ContestScanner();
        int n = sc.nextInt();
        long k = sc.nextLong();
        var ka = new long[16];
        ka[0] = 1;
        for (int i = 1; i < 16; i++)
            ka[i] = i * ka[i - 1];
        var a = new int[n];
        int cn = 0;
        for (int i = 1; i <= 9; i++) {
            int nc = sc.nextInt();
            for (int j = 0; j < nc; j++)
                a[cn++] = i;
        }
        if (n < 7) {
            var r = new HashSet<Long>();
            for (var i : new Permutation(n)) {
                long s = 0;
                for (int j : i) {
                    s *= 10;
                    s += a[j];
                }
                if (s % k == 0)
                    r.add(s);
            }
            System.out.println(r.size());
            return;
        }
        int nn = n >> 1, mm = n - nn;
        int ma = 1 << n;
        long m10 = mp(10, mm, k);
        var aa = new HashMap<Long, Long>();
        var bb = new HashMap<Long, Long>();
        var xx = new HashSet<String>();
        var aaa = new int[nn];
        var bbb = new int[mm];
        long ans = 0;
        var tt = new int[9];
        for (int bi = (1 << nn) - 1; bi < ma; bi = n(bi)) {
            aa.clear();
            bb.clear();
            int ii = bi, cc = 0, ccc = 0;
            var ss = new StringBuilder();
            for (int i = 0; i < n; i++) {
                if ((ii & 1) == 1) {
                    aaa[cc] = a[i];
                    ss.append(String.valueOf(aaa[cc]));
                    cc++;
                } else {
                    bbb[ccc] = a[i];
                    ccc++;
                }
                ii >>= 1;
            }
            var rr = ss.toString();
            if (xx.contains(rr))
                continue;
            xx.add(rr);
            for (var i : new Permutation(nn)) {
                long s = 0;
                for (int j : i) {
                    s *= 10;
                    s += aaa[j];
                }
                s *= m10;
                s %= k;
                if (aa.containsKey(s))
                    aa.put(s, aa.get(s) + 1L);
                else
                    aa.put(s, 1L);
            }
            for (var i : new Permutation(mm)) {
                long s = 0;
                for (int j : i) {
                    s *= 10;
                    s += bbb[j];
                }
                s = -s;
                s %= k;
                if (s < 0)
                    s += k;
                if (bb.containsKey(s))
                    bb.put(s, bb.get(s) + 1L);
                else
                    bb.put(s, 1L);
            }
            var r = new A();
            aa.forEach((i, j) -> {
                if (bb.containsKey(i))
                    r.a(j * bb.get(i));
            });
            long tr = r.a;
            Arrays.fill(tt, 0);
            for (int i : aaa)
                tt[i - 1]++;
            for (int i : tt)
                tr /= ka[i];
            Arrays.fill(tt, 0);
            for (int i : bbb)
                tt[i - 1]++;
            for (int i : tt)
                tr /= ka[i];
            ans += tr;
        }
        System.out.println(ans);
    }

    private static long mp(long a, long b, long m) {
        if (b == 0)
            return 1;
        if ((b & 1) == 1)
            return (a * mp(a, b - 1, m)) % m;
        return mp((a * a) % m, b >> 1, m);
    }

    private static int n(int s) {
        int x = s & -s, y = s + x;
        return (((s & ~y) / x) >> 1) | y;
    }
}

class A {
    long a = 0L;

    public void a(long x) {
        a += x;
    }

    public void d(long x) {
        a /= x;
    }

    public long g() {
        return a;
    }

    @Override
    public String toString() {
        return String.valueOf(a);
    }
}

class Permutation implements java.util.Iterator<int[]>, Iterable<int[]> {
    private int[] next;

    public Permutation(int n) {
        next = java.util.stream.IntStream.range(0, n).toArray();
    }

    @Override
    public boolean hasNext() {
        return next != null;
    }

    @Override
    public int[] next() {
        int[] r = next.clone();
        next = nextPermutation(next);
        return r;
    }

    @Override
    public java.util.Iterator<int[]> iterator() {
        return this;
    }

    public static int[] nextPermutation(int[] a) {
        if (a == null || a.length < 2)
            return null;
        int p = 0;
        for (int i = a.length - 2; i >= 0; i--) {
            if (a[i] >= a[i + 1])
                continue;
            p = i;
            break;
        }
        int q = 0;
        for (int i = a.length - 1; i > p; i--) {
            if (a[i] <= a[p])
                continue;
            q = i;
            break;
        }
        if (p == 0 && q == 0)
            return null;
        int temp = a[p];
        a[p] = a[q];
        a[q] = temp;
        int l = p, r = a.length;
        while (++l < --r) {
            temp = a[l];
            a[l] = a[r];
            a[r] = temp;
        }
        return a;
    }
}

class ContestScanner {
    private final InputStream in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;

    public ContestScanner(InputStream in) {
        this.in = in;
    }

    public ContestScanner() {
        this(System.in);
    }

    private boolean hasNextByte() {
        if (ptr < buflen)
            return true;
        ptr = 0;
        try {
            buflen = in.read(buffer);
        } catch (IOException e) {
            e.printStackTrace();
        }
        return buflen > 0;
    }

    private int readByte() {
        return hasNextByte() ? buffer[ptr++] : -1;
    }

    private static boolean isPrintableChar(int c) {
        return 33 <= c && c <= 126;
    }

    public boolean hasNext() {
        while (hasNextByte() && !isPrintableChar(buffer[ptr]))
            ptr++;
        return hasNextByte();
    }

    public String next() {
        if (!hasNext())
            throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while (isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    public void nextThrow(int n) {
        for (int i = 0; i < n; i++)
            this.next();
    }

    public void nextThrow() {
        this.nextThrow(1);
    }

    public long nextLong() {
        if (!hasNext())
            throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b)
            throw new NumberFormatException();
        while (true) {
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            } else if (b == -1 || !isPrintableChar(b))
                return minus ? -n : n;
            else
                throw new NumberFormatException();
            b = readByte();
        }
    }

    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
            throw new NumberFormatException();
        return (int) nl;
    }

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

    public boolean[] nextBoolean(char True) {
        String s = this.next();
        int n = s.length();
        boolean[] array = new boolean[n];
        for (int i = 0; i < n; i++)
            array[i] = s.charAt(i) == True;
        return array;
    }

    public long[] nextLongArray(int length) {
        long[] array = new long[length];
        for (int i = 0; i < length; i++)
            array[i] = this.nextLong();
        return array;
    }

    public long[] nextLongArray(int length, java.util.function.LongUnaryOperator map) {
        long[] array = new long[length];
        for (int i = 0; i < length; i++)
            array[i] = map.applyAsLong(this.nextLong());
        return array;
    }

    public long[] nextLongArray(int length, long[] a) {
        long[] array = new long[length + a.length];
        for (int i = 0; i < length; i++)
            array[i] = this.nextLong();
        for (int i = length; i < array.length; i++)
            array[i] = a[i - length];
        return array;
    }

    public int[] nextIntArray(int length) {
        int[] array = new int[length];
        for (int i = 0; i < length; i++)
            array[i] = this.nextInt();
        return array;
    }

    public int[] nextIntArray(int length, java.util.function.IntUnaryOperator map) {
        int[] array = new int[length];
        for (int i = 0; i < length; i++)
            array[i] = map.applyAsInt(this.nextInt());
        return array;
    }

    public int[] nextIntArray(int length, int[] array) {
        int n = length + array.length;
        int[] a = new int[n];
        for (int i = 0; i < length; i++)
            a[i] = this.nextInt();
        for (int i = length; i < n; i++)
            a[i] = array[i - length];
        return a;
    }

    public Integer[] nextIntegerArray(int length, java.util.function.IntUnaryOperator map) {
        Integer[] array = new Integer[length];
        for (int i = 0; i < length; i++)
            array[i] = map.applyAsInt(this.nextInt());
        return array;
    }

    public Integer[] nextIntegerArray(int length) {
        Integer[] array = new Integer[length];
        for (int i = 0; i < length; i++)
            array[i] = this.nextInt();
        return array;
    }

    public double[] nextDoubleArray(int length) {
        double[] array = new double[length];
        for (int i = 0; i < length; i++)
            array[i] = this.nextDouble();
        return array;
    }

    public double[] nextDoubleArray(int length, java.util.function.DoubleUnaryOperator map) {
        double[] array = new double[length];
        for (int i = 0; i < length; i++)
            array[i] = map.applyAsDouble(this.nextDouble());
        return array;
    }

    public String[] nextArray(int length) {
        String[] array = new String[length];
        for (int i = 0; i < length; i++)
            array[i] = this.next();
        return array;
    }

    public long[][] nextLongMatrix(int height, int width) {
        long[][] mat = new long[height][width];
        for (int h = 0; h < height; h++)
            for (int w = 0; w < width; w++)
                mat[h][w] = this.nextLong();
        return mat;
    }

    public int[][] nextIntMatrix(int height, int width) {
        int[][] mat = new int[height][width];
        for (int h = 0; h < height; h++)
            for (int w = 0; w < width; w++)
                mat[h][w] = this.nextInt();
        return mat;
    }

    public int[][] nextIntMatrix(int height, int width, java.util.function.IntUnaryOperator map) {
        int[][] mat = new int[height][width];
        for (int h = 0; h < height; h++)
            for (int w = 0; w < width; w++)
                mat[h][w] = map.applyAsInt(this.nextInt());
        return mat;
    }

    public double[][] nextDoubleMatrix(int height, int width) {
        double[][] mat = new double[height][width];
        for (int h = 0; h < height; h++)
            for (int w = 0; w < width; w++)
                mat[h][w] = this.nextDouble();
        return mat;
    }

    public boolean[][] nextBooleanMatrix(int height, int width, char True) {
        boolean[][] mat = new boolean[height][width];
        for (int h = 0; h < height; h++) {
            String s = this.next();
            for (int w = 0; w < width; w++)
                mat[h][w] = s.charAt(w) == True;
        }
        return mat;
    }

    public char[][] nextCharMatrix(int height, int width) {
        char[][] mat = new char[height][width];
        for (int h = 0; h < height; h++) {
            String s = this.next();
            for (int w = 0; w < width; w++)
                mat[h][w] = s.charAt(w);
        }
        return mat;
    }

    public char[][] nextCharMatrix(int height, int width, int h, int w, char c) {
        char[][] mat = new char[height + 2 * h][width + 2 * w];
        for (int i = 0; i < height; i++) {
            String s = this.next();
            for (int j = 0; j < width; j++)
                mat[i + h][j + w] = s.charAt(j);
        }
        for (int i = 0; i < h; i++)
            for (int j = 0; j < 2 * w + width; j++)
                mat[i][j] = c;
        for (int i = h + height; i < 2 * h + height; i++)
            for (int j = 0; j < 2 * w + width; j++)
                mat[i][j] = c;
        for (int i = h; i < h + height; i++) {
            for (int j = 0; j < w; j++)
                mat[i][j] = c;
            for (int j = w + width; j < 2 * w + width; j++)
                mat[i][j] = c;
        }
        return mat;
    }

    public boolean[][] nextBooleanMatrix(int height, int width, int h, int w, char c) {
        boolean[][] mat = new boolean[height + 2 * h][width + 2 * w];
        for (int i = 0; i < height; i++) {
            String s = this.next();
            for (int j = 0; j < width; j++)
                mat[i + h][j + w] = s.charAt(j) == c;
        }
        return mat;
    }
}

yukicoder

結果

テストケース

ソースコード