結果
問題 | No.2067 ±2^k operations |
ユーザー |
![]() |
提出日時 | 2022-08-28 23:39:43 |
言語 | Java (openjdk 23) |
結果 |
TLE
|
実行時間 | - |
コード長 | 23,058 bytes |
コンパイル時間 | 3,250 ms |
コンパイル使用メモリ | 92,792 KB |
実行使用メモリ | 81,992 KB |
最終ジャッジ日時 | 2024-10-15 20:06:55 |
合計ジャッジ時間 | 7,460 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | TLE * 1 -- * 22 |
ソースコード
import java.util.*;import java.io.*;class Main {private static final void solve() throws IOException {f.clear();long n = nl();ou.println(s(n));}private static final long s(long n) {if (n == 0)return 0;if ((n & 1) == 1) {return s(n - 1) + f(n);}return (s(n >> 1) << 1) + b(n >> 1) + c(n >> 1);}private static HashMap<Long, Long> f = new HashMap<>();private static final long f(long n) {if (n <= 1)return n;if (f.containsKey(n))return f.get(n);long ans = (n & 1) == 1 ? Math.min(f((n + 1) >> 1), f((n - 1) >> 1)) + 1 : f(n >> 1);f.put(n, ans);return ans;}private static final long a(long n) {if (n == 0)return 0;if ((n & 1) == 1) {long ans = a(n - 1);if (f(n - 1) < f(n))ans++;return ans;}return a(n >> 1) + b(n >> 1);}private static final long b(long n) {if (n == 0)return 0;if ((n & 1) == 1) {long ans = b(n - 1);if (f(n - 1) == f(n))ans++;return ans;}return a(n >> 1) + c(n >> 1);}private static final long c(long n) {if (n == 0)return 0;if ((n & 1) == 1) {long ans = c(n - 1);if (f(n - 1) > f(n))ans++;return ans;}return b(n >> 1) + c(n >> 1);}public static void main(String[] args) throws IOException {int t = ni();for (int i = 0; i < t; i++)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();}class DSU {private int n;private int[] parentOrSize;public DSU(int n) {this.n = n;this.parentOrSize = new int[n];java.util.Arrays.fill(parentOrSize, -1);}int merge(int a, int b) {if (!(0 <= a && a < n))throw new IndexOutOfBoundsException("a=" + a);if (!(0 <= b && b < n))throw new IndexOutOfBoundsException("b=" + b);int x = leader(a);int y = leader(b);if (x == y)return x;if (-parentOrSize[x] < -parentOrSize[y]) {int tmp = x;x = y;y = tmp;}parentOrSize[x] += parentOrSize[y];parentOrSize[y] = x;return x;}boolean same(int a, int b) {if (!(0 <= a && a < n))throw new IndexOutOfBoundsException("a=" + a);if (!(0 <= b && b < n))throw new IndexOutOfBoundsException("b=" + b);return leader(a) == leader(b);}int leader(int a) {if (parentOrSize[a] < 0) {return a;} else {parentOrSize[a] = leader(parentOrSize[a]);return parentOrSize[a];}}int size(int a) {if (!(0 <= a && a < n))throw new IndexOutOfBoundsException("" + a);return -parentOrSize[leader(a)];}ArrayList<ArrayList<Integer>> groups() {int[] leaderBuf = new int[n];int[] groupSize = new int[n];for (int i = 0; i < n; i++) {leaderBuf[i] = leader(i);groupSize[leaderBuf[i]]++;}ArrayList<ArrayList<Integer>> result = new ArrayList<>(n);for (int i = 0; i < n; i++)result.add(new ArrayList<>(groupSize[i]));for (int i = 0; i < n; i++)result.get(leaderBuf[i]).add(i);result.removeIf(ArrayList::isEmpty);return result;}}class LCA {private int log_n;private ArrayList<ArrayList<Integer>> g;private int[][] parent;private int[] depth;LCA(int n, ArrayList<ArrayList<Integer>> g) {this.g = g;int c = 0;int nn = 1;while (nn <= n) {c++;nn <<= 1;}log_n = c;parent = new int[log_n][n];depth = new int[n];dfs(0, -1, 0);for (int k = 1; k < log_n; k++)for (int v = 0; v < n; v++)parent[k][v] = parent[k - 1][v] < 0 ? -1 : parent[k - 1][parent[k - 1][v]];}void dfs(int v, int p, int d) {parent[0][v] = p;depth[v] = d;for (int i : g.get(v)) {if (i != p)dfs(i, v, d + 1);}}int lca(int u, int v) {if (depth[u] > depth[v]) {int tmp = u;u = v;v = tmp;}for (int k = 0; k < log_n; k++)if (((depth[v] - depth[u]) >> k & 1) == 1)v = parent[k][v];if (u == v)return u;for (int k = log_n - 1; k >= 0; k--) {if (parent[k][u] != parent[k][v]) {u = parent[k][u];v = parent[k][v];}}return parent[0][u];}int dist(int u, int v) {return depth[u] + depth[v] - 2 * depth[lca(u, v)];}}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 << 20];}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;}@Overridepublic final int available() throws IOException {if (pos < lim)return lim - pos + in.available();return in.available();}@Overridepublic 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);}@Overridepublic final int read() throws IOException {if (hasRemaining())return buf[pos++];return -1;}@Overridepublic 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 int[][] nextIntMatrix(int h, int w, java.util.function.IntUnaryOperator map) 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] = map.applyAsInt(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;}public final void nextThrow() throws IOException {next();return;}public final void nextThrow(int n) throws IOException {for (int i = 0; i < n; i++)nextThrow();return;}}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];}@Overridepublic 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;}@Overridepublic void write(int b) throws IOException {put((byte) b);}@Overridepublic 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;}}@Overridepublic ContestOutputStream append(char c) throws IOException {put((byte) c);return this;}@Overridepublic 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;}@Overridepublic 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 newLine();}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 {if (!arr.isEmpty()) {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;}public ContestOutputStream println() throws IOException {return newLine();}}