#761472 (Java21) No.1935 Water Simulation

提出ソース
結果

問題	No.1935 Water Simulation
ユーザー	遭難者
提出日時	2022-05-16 10:07:25
言語	Java21 (openjdk 21)
結果	MLE
実行時間	-
コード長	22,035 bytes
コンパイル時間	2,961 ms
コンパイル使用メモリ	80,732 KB
実行使用メモリ	747,624 KB
最終ジャッジ日時	2023-10-12 02:07:50
合計ジャッジ時間	16,307 ms
ジャッジサーバーID （参考情報）	judge12 / judge14
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	MLE	-
testcase_01	MLE	-
testcase_02	AC	45 ms 49,032 KB
testcase_03	MLE	-
testcase_04	AC	195 ms 187,548 KB
testcase_05	MLE	-
testcase_06	MLE	-
testcase_07	AC	280 ms 313,276 KB
testcase_08	AC	325 ms 352,628 KB
testcase_09	MLE	-
testcase_10	MLE	-
testcase_11	AC	284 ms 229,664 KB
testcase_12	AC	46 ms 48,688 KB
testcase_13	AC	43 ms 49,040 KB
testcase_14	AC	151 ms 114,816 KB
testcase_15	AC	372 ms 468,468 KB
testcase_16	AC	392 ms 454,048 KB
testcase_17	AC	245 ms 212,128 KB
testcase_18	AC	45 ms 48,760 KB
testcase_19	MLE	-
testcase_20	AC	75 ms 62,408 KB
testcase_21	AC	411 ms 452,156 KB
testcase_22	MLE	-
testcase_23	AC	152 ms 114,216 KB
testcase_24	MLE	-
testcase_25	MLE	-
testcase_26	AC	54 ms 53,348 KB
testcase_27	AC	198 ms 187,448 KB
testcase_28	AC	171 ms 131,224 KB
testcase_29	AC	44 ms 48,848 KB
testcase_30	AC	47 ms 50,892 KB
testcase_31	AC	109 ms 86,084 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
import java.util.*;
import java.io.*;

class Main {
    private static final void solve() throws IOException {
        int v1 = ni(), v2 = ni(), v3 = ni(), v4 = ni();
        int vv = (v1 + 1) * (v1 + 1), vvv = vv * (v1 + 1);
        var a1 = new int[60][vvv];
        var a2 = new int[60][vvv];
        var a3 = new int[60][vvv];
        var a4 = new int[60][vvv];
        for (int i = 0; i <= v1; i++) {
            for (int j = 0; j <= v2; j++) {
                int s1 = i + j;
                if (s1 > v1)
                    break;
                for (int k = 0; k <= v3; k++) {
                    int s2 = s1 + k;
                    if (s2 > v1)
                        break;
                    int key = vv * i + v1 * j + k;
                    int l = v1 - s2;
                    int ii = i, jj = j, kk = k, ll = l;
                    jj += ii;
                    ii = 0;
                    if (jj > v2) {
                        ii = jj - v2;
                        jj = v2;
                    }
                    kk += jj;
                    jj = 0;
                    if (kk > v3) {
                        jj = kk - v3;
                        kk = v3;
                    }
                    ll += kk;
                    kk = 0;
                    if (ll > v4) {
                        kk = ll - v4;
                        ll = v4;
                    }
                    ii += ll;
                    ll = 0;
                    if (ii > v1) {
                        ll = ii - v1;
                        ii = v1;
                    }
                    a1[0][key] = ii;
                    a2[0][key] = jj;
                    a3[0][key] = kk;
                    a4[0][key] = ll;
                }
            }
        }
        for (int idx = 1; idx < 60; idx++) {
            for (int i = 0; i <= v1; i++) {
                for (int j = 0; j <= v2; j++) {
                    int s1 = i + j;
                    if (s1 > v1)
                        break;
                    for (int k = 0; k <= v3; k++) {
                        int s2 = s1 + k;
                        if (s2 > v1)
                            break;
                        // int l = v1 - s2;
                        int key1 = vv * i + v1 * j + k;
                        int ii = a1[idx - 1][key1];
                        int jj = a2[idx - 1][key1];
                        int kk = a3[idx - 1][key1];
                        // int ll = a4[idx - 1][key1];
                        int key2 = vv * ii + v1 * jj + kk;
                        int iii = a1[idx - 1][key2];
                        int jjj = a2[idx - 1][key2];
                        int kkk = a3[idx - 1][key2];
                        int lll = a4[idx - 1][key2];
                        a1[idx][key1] = iii;
                        a2[idx][key1] = jjj;
                        a3[idx][key1] = kkk;
                        a4[idx][key1] = lll;
                    }
                }
            }
        }
        long k_ = nl(), k1 = k_ >> 2, k2 = k_ & 3;
        int i = v1, j = 0, k = 0, l = 0;
        for (int idx = 0; k1 != 0; idx++) {
            if ((k1 & 1) == 1) {
                int key = vv * i + v1 * j + k;
                int ii = a1[idx][key];
                int jj = a2[idx][key];
                int kk = a3[idx][key];
                int ll = a4[idx][key];
                i = ii;
                j = jj;
                k = kk;
                l = ll;
            }
            k1 >>= 1;
        }
        if (k2 == 0) {
            ou.print(i).print(" ").print(j).print(" ").print(k).print(" ").print(l).newLine();
            return;
        }
        j += i;
        i = 0;
        if (j > v2) {
            i = j - v2;
            j = v2;
        }
        if (--k2 == 0) {
            ou.print(i).print(" ").print(j).print(" ").print(k).print(" ").print(l).newLine();
            return;
        }
        k += j;
        j = 0;
        if (k > v3) {
            j = k - v3;
            k = v3;
        }
        if (--k2 == 0) {
            ou.print(i).print(" ").print(j).print(" ").print(k).print(" ").print(l).newLine();
            return;
        }
        l += k;
        k = 0;
        if (l > v4) {
            k = l - v4;
            l = v4;
        }
        if (--k2 == 0) {
            ou.print(i).print(" ").print(j).print(" ").print(k).print(" ").print(l).newLine();
            return;
        }
        i += l;
        l = 0;
        if (i > v1) {
            l = i - v1;
            i = v1;
        }
        if (--k2 == 0) {
            ou.print(i).print(" ").print(j).print(" ").print(k).print(" ").print(l).newLine();
            return;
        }
    }

    public static void main(String[] args) throws IOException {
        solve();
        ou.flush();
    }

    private static final int ni() throws IOException {
        return sc.nextInt();
    }

    private static final int[] ni(int n) throws IOException {
        return sc.nextIntArray(n);
    }

    private static final long nl() throws IOException {
        return sc.nextLong();
    }

    private static final long[] nl(int n) throws IOException {
        return sc.nextLongArray(n);
    }

    private static final String ns() throws IOException {
        return sc.next();
    }

    private static final ContestInputStream sc = new ContestInputStream();
    private static final ContestOutputStream ou = new ContestOutputStream();
}

final class ContestInputStream extends FilterInputStream {
    protected final byte[] buf;
    protected int pos = 0;
    protected int lim = 0;
    private final char[] cbuf;

    public ContestInputStream() {
        super(System.in);
        this.buf = new byte[1 << 13];
        this.cbuf = new char[1 << 19];
    }

    boolean hasRemaining() throws IOException {
        if (pos < lim)
            return true;
        lim = in.read(buf);
        pos = 0;
        return lim > 0;
    }

    final int remaining() throws IOException {
        if (pos >= lim) {
            lim = in.read(buf);
            pos = 0;
        }
        return lim - pos;
    }

    @Override
    public final int available() throws IOException {
        if (pos < lim)
            return lim - pos + in.available();
        return in.available();
    }

    @Override
    public final long skip(long n) throws IOException {
        if (pos < lim) {
            int rem = lim - pos;
            if (n < rem) {
                pos += n;
                return n;
            }
            pos = lim;
            return rem;
        }
        return in.skip(n);
    }

    @Override
    public final int read() throws IOException {
        if (hasRemaining())
            return buf[pos++];
        return -1;
    }

    @Override
    public final int read(byte[] b, int off, int len) throws IOException {
        if (pos < lim) {
            int rem = Math.min(lim - pos, len);
            for (int i = 0; i < rem; i++)
                b[off + i] = buf[pos + i];
            pos += rem;
            return rem;
        }
        return in.read(b, off, len);
    }

    public final char[] readToken() throws IOException {
        int cpos = 0;
        int rem;
        int i;
        byte b;
        l: while ((rem = remaining()) > 0) {
            for (i = 0; i < rem; i++) {
                b = buf[pos + i];
                if (b <= 0x20) {
                    pos += i + 1;
                    cpos += i;
                    break l;
                }
                cbuf[cpos + i] = (char) b;
            }
            pos += rem;
            cpos += rem;
        }
        char[] arr = new char[cpos];
        for (i = 0; i < cpos; i++)
            arr[i] = cbuf[i];
        return arr;
    }

    public final int readToken(char[] cbuf, int off) throws IOException {
        int cpos = off;
        int rem;
        int i;
        byte b;
        l: while ((rem = remaining()) > 0) {
            for (i = 0; i < rem; i++) {
                b = buf[pos + i];
                if (b <= 0x20) {
                    pos += i + 1;
                    cpos += i;
                    break l;
                }
                cbuf[cpos + i] = (char) b;
            }
            pos += rem;
            cpos += rem;
        }
        return cpos - off;
    }

    public final int readToken(char[] cbuf) throws IOException {
        return readToken(cbuf, 0);
    }

    public final String next() throws IOException {
        int cpos = 0;
        int rem;
        int i;
        byte b;
        l: while ((rem = remaining()) > 0) {
            for (i = 0; i < rem; i++) {
                b = buf[pos + i];
                if (b <= 0x20) {
                    pos += i + 1;
                    cpos += i;
                    break l;
                }
                cbuf[cpos + i] = (char) b;
            }
            pos += rem;
            cpos += rem;
        }
        return String.valueOf(cbuf, 0, cpos);
    }

    public final int nextInt() throws IOException {
        if (!hasRemaining())
            return 0;
        int value = 0;
        byte b = buf[pos++];
        if (b == 0x2d) {
            while (hasRemaining() && (b = buf[pos++]) > 0x20)
                value = value * 10 - b + 0x30;
        } else {
            do {
                value = value * 10 + b - 0x30;
            } while (hasRemaining() && (b = buf[pos++]) > 0x20);
        }
        return value;
    }

    public final long nextLong() throws IOException {
        if (!hasRemaining())
            return 0L;
        long value = 0L;
        byte b = buf[pos++];
        if (b == 0x2d) {
            while (hasRemaining() && (b = buf[pos++]) > 0x20)
                value = value * 10 - b + 0x30;
        } else {
            do {
                value = value * 10 + b - 0x30;
            } while (hasRemaining() && (b = buf[pos++]) > 0x20);
        }
        return value;
    }

    public final float nextFloat() throws IOException {
        return Float.parseFloat(next());
    }

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

    public final boolean[] nextBooleanArray(char ok) throws IOException {
        char[] s = next().toCharArray();
        int n = s.length;
        boolean[] t = new boolean[n];
        for (int i = 0; i < n; i++)
            t[i] = s[i] == ok;
        return t;
    }

    public final boolean[][] nextBooleanMatrix(int h, int w, char ok) throws IOException {
        boolean[][] s = new boolean[h][];
        for (int i = 0; i < h; i++) {
            char[] t = next().toCharArray();
            int n = t.length;
            s[i] = new boolean[n];
            for (int j = 0; j < n; j++)
                s[i][j] = t[j] == ok;
        }
        return s;
    }

    public final String[] nextStringArray(int len) throws IOException {
        String[] arr = new String[len];
        for (int i = 0; i < len; i++)
            arr[i] = next();
        return arr;
    }

    public final int[] nextIntArray(int len) throws IOException {
        int[] arr = new int[len];
        for (int i = 0; i < len; i++)
            arr[i] = nextInt();
        return arr;
    }

    public final int[] nextIntArray(int len, java.util.function.IntUnaryOperator map) throws IOException {
        int[] arr = new int[len];
        for (int i = 0; i < len; i++)
            arr[i] = map.applyAsInt(nextInt());
        return arr;
    }

    public final long[] nextLongArray(int len, java.util.function.LongUnaryOperator map) throws IOException {
        long[] arr = new long[len];
        for (int i = 0; i < len; i++)
            arr[i] = map.applyAsLong(nextLong());
        return arr;
    }

    public final int[][] nextIntMatrix(int h, int w) throws IOException {
        int[][] arr = new int[h][w];
        for (int i = 0; i < h; i++)
            for (int j = 0; j < w; j++)
                arr[i][j] = nextInt();
        return arr;
    }

    public final long[] nextLongArray(int len) throws IOException {
        long[] arr = new long[len];
        for (int i = 0; i < len; i++)
            arr[i] = nextLong();
        return arr;
    }

    public final long[][] nextLongMatrix(int h, int w) throws IOException {
        long[][] arr = new long[h][w];
        for (int i = 0; i < h; i++)
            for (int j = 0; j < w; j++)
                arr[i][j] = nextLong();
        return arr;
    }

    public final float[] nextFloatArray(int len) throws IOException {
        float[] arr = new float[len];
        for (int i = 0; i < len; i++)
            arr[i] = nextFloat();
        return arr;
    }

    public final double[] nextDoubleArray(int len) throws IOException {
        double[] arr = new double[len];
        for (int i = 0; i < len; i++)
            arr[i] = nextDouble();
        return arr;
    }

    public final char[][] nextCharMatrix(int h, int w) throws IOException {
        char[][] arr = new char[h][];
        for (int i = 0; i < h; i++)
            arr[i] = next().toCharArray();
        return arr;
    }
}

final class ContestOutputStream extends FilterOutputStream implements Appendable {
    protected final byte[] buf;
    protected int pos = 0;

    public ContestOutputStream() {
        super(System.out);
        this.buf = new byte[1 << 13];
    }

    @Override
    public void flush() throws IOException {
        out.write(buf, 0, pos);
        pos = 0;
        out.flush();
    }

    void put(byte b) throws IOException {
        if (pos >= buf.length)
            flush();
        buf[pos++] = b;
    }

    int remaining() throws IOException {
        if (pos >= buf.length)
            flush();
        return buf.length - pos;
    }

    @Override
    public void write(int b) throws IOException {
        put((byte) b);
    }

    @Override
    public void write(byte[] b, int off, int len) throws IOException {
        int o = off;
        int l = len;
        while (l > 0) {
            int rem = Math.min(remaining(), l);
            for (int i = 0; i < rem; i++)
                buf[pos + i] = b[o + i];
            pos += rem;
            o += rem;
            l -= rem;
        }
    }

    @Override
    public ContestOutputStream append(char c) throws IOException {
        put((byte) c);
        return this;
    }

    @Override
    public ContestOutputStream append(CharSequence csq, int start, int end) throws IOException {
        int off = start;
        int len = end - start;
        while (len > 0) {
            int rem = Math.min(remaining(), len);
            for (int i = 0; i < rem; i++)
                buf[pos + i] = (byte) csq.charAt(off + i);
            pos += rem;
            off += rem;
            len -= rem;
        }
        return this;
    }

    @Override
    public ContestOutputStream append(CharSequence csq) throws IOException {
        return append(csq, 0, csq.length());
    }

    public ContestOutputStream append(char[] arr, int off, int len) throws IOException {
        int o = off;
        int l = len;
        while (l > 0) {
            int rem = Math.min(remaining(), l);
            for (int i = 0; i < rem; i++)
                buf[pos + i] = (byte) arr[o + i];
            pos += rem;
            o += rem;
            l -= rem;
        }

        return this;
    }

    public ContestOutputStream print(char[] arr) throws IOException {
        return append(arr, 0, arr.length).newLine();
    }

    public ContestOutputStream print(boolean value) throws IOException {
        if (value)
            return append("o");
        return append("x");
    }

    public ContestOutputStream println(boolean value) throws IOException {
        if (value)
            return append("o\n");
        return append("x\n");
    }

    public ContestOutputStream print(boolean[][] value) throws IOException {
        final int n = value.length, m = value[0].length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++)
                print(value[i][j]);
            newLine();
        }
        return this;
    }

    public ContestOutputStream print(int value) throws IOException {
        return append(String.valueOf(value));
    }

    public ContestOutputStream println(int value) throws IOException {
        return append(String.valueOf(value)).newLine();
    }

    public ContestOutputStream print(long value) throws IOException {
        return append(String.valueOf(value));
    }

    public ContestOutputStream println(long value) throws IOException {
        return append(String.valueOf(value)).newLine();
    }

    public ContestOutputStream print(float value) throws IOException {
        return append(String.valueOf(value));
    }

    public ContestOutputStream println(float value) throws IOException {
        return append(String.valueOf(value)).newLine();
    }

    public ContestOutputStream print(double value) throws IOException {
        return append(String.valueOf(value));
    }

    public ContestOutputStream println(double value) throws IOException {
        return append(String.valueOf(value)).newLine();
    }

    public ContestOutputStream print(char value) throws IOException {
        return append(String.valueOf(value));
    }

    public ContestOutputStream println(char value) throws IOException {
        return append(String.valueOf(value)).newLine();
    }

    public ContestOutputStream print(String value) throws IOException {
        return append(String.valueOf(value));
    }

    public ContestOutputStream println(String value) throws IOException {
        return append(String.valueOf(value)).newLine();
    }

    public ContestOutputStream print(Object value) throws IOException {
        return append(String.valueOf(value));
    }

    public ContestOutputStream println(Object value) throws IOException {
        return append(String.valueOf(value)).newLine();
    }

    public ContestOutputStream printYN(boolean yes) throws IOException {
        if (yes)
            return println("Yes");
        return println("No");
    }

    public ContestOutputStream print(CharSequence[] arr) throws IOException {
        if (arr.length > 0) {
            append(arr[0]);
            for (int i = 1; i < arr.length; i++)
                append('\u0020').append(arr[i]);
        }
        return this;
    }

    public ContestOutputStream print(int[] arr) throws IOException {
        if (arr.length > 0) {
            print(arr[0]);
            for (int i = 1; i < arr.length; i++)
                append('\u0020').print(arr[i]);
        }
        newLine();
        return this;
    }

    public ContestOutputStream println(int[] arr) throws IOException {
        for (int i : arr)
            print(i).newLine();
        return this;
    }

    public ContestOutputStream print(boolean[] arr) throws IOException {
        if (arr.length > 0) {
            print(arr[0]);
            for (int i = 1; i < arr.length; i++)
                append('\u0020').print(arr[i]);
        }
        newLine();
        return this;
    }

    public ContestOutputStream print(long[] arr) throws IOException {
        if (arr.length > 0) {
            print(arr[0]);
            for (int i = 1; i < arr.length; i++)
                append('\u0020').print(arr[i]);
        }
        newLine();
        return this;
    }

    public ContestOutputStream println(long[] arr) throws IOException {
        for (long i : arr)
            print(i).newLine();
        return this;
    }

    public ContestOutputStream print(float[] arr) throws IOException {
        if (arr.length > 0) {
            print(arr[0]);
            for (int i = 1; i < arr.length; i++)
                append('\u0020').print(arr[i]);
        }
        return this;
    }

    public ContestOutputStream println(float[] arr) throws IOException {
        for (float i : arr)
            print(i).newLine();
        return this;
    }

    public ContestOutputStream print(double[] arr) throws IOException {
        if (arr.length > 0) {
            print(arr[0]);
            for (int i = 1; i < arr.length; i++)
                append('\u0020').print(arr[i]);
        }
        return this;
    }

    public ContestOutputStream println(double[] arr) throws IOException {
        for (double i : arr)
            print(i).newLine();
        return this;
    }

    public ContestOutputStream print(Object[] arr) throws IOException {
        if (arr.length > 0) {
            print(arr[0]);
            for (int i = 1; i < arr.length; i++)
                append('\u0020').print(arr[i]);
        }
        return newLine();
    }

    public ContestOutputStream print(java.util.ArrayList<?> arr) throws IOException {
        final int n = arr.size();
        print(arr.get(0));
        for (int i = 1; i < n; i++)
            print(" ").print(arr.get(i));
        return newLine();
    }

    public ContestOutputStream println(java.util.ArrayList<?> arr) throws IOException {
        final int n = arr.size();
        for (int i = 0; i < n; i++)
            println(arr.get(i));
        return this;
    }

    public ContestOutputStream println(Object[] arr) throws IOException {
        for (Object i : arr)
            print(i).newLine();
        return this;
    }

    public ContestOutputStream newLine() throws IOException {
        return append('\n');
    }

    public ContestOutputStream endl() throws IOException {
        newLine().flush();
        return this;
    }

    public ContestOutputStream print(int[][] arr) throws IOException {
        for (int[] i : arr)
            print(i);
        return this;
    }

    public ContestOutputStream print(long[][] arr) throws IOException {
        for (long[] i : arr)
            print(i);
        return this;
    }

    public ContestOutputStream print(char[][] arr) throws IOException {
        for (char[] i : arr)
            print(i);
        return this;
    }

    public ContestOutputStream print(Object[][] arr) throws IOException {
        for (Object[] i : arr)
            print(i);
        return this;
    }
}
yukicoder

結果

テストケース

ソースコード
