結果
問題 | No.130 XOR Minimax |
ユーザー | Grenache |
提出日時 | 2016-06-15 19:24:50 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 1,580 ms / 5,000 ms |
コード長 | 2,328 bytes |
コンパイル時間 | 3,941 ms |
コンパイル使用メモリ | 77,100 KB |
実行使用メモリ | 89,660 KB |
最終ジャッジ日時 | 2023-10-10 00:15:38 |
合計ジャッジ時間 | 22,420 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 963 ms
78,148 KB |
testcase_01 | AC | 45 ms
49,724 KB |
testcase_02 | AC | 45 ms
49,672 KB |
testcase_03 | AC | 45 ms
49,916 KB |
testcase_04 | AC | 181 ms
58,868 KB |
testcase_05 | AC | 255 ms
62,828 KB |
testcase_06 | AC | 576 ms
79,208 KB |
testcase_07 | AC | 655 ms
83,084 KB |
testcase_08 | AC | 1,580 ms
88,976 KB |
testcase_09 | AC | 263 ms
56,984 KB |
testcase_10 | AC | 330 ms
59,624 KB |
testcase_11 | AC | 645 ms
72,392 KB |
testcase_12 | AC | 211 ms
56,820 KB |
testcase_13 | AC | 500 ms
68,460 KB |
testcase_14 | AC | 1,430 ms
87,560 KB |
testcase_15 | AC | 125 ms
56,156 KB |
testcase_16 | AC | 1,223 ms
80,676 KB |
testcase_17 | AC | 1,227 ms
80,116 KB |
testcase_18 | AC | 1,221 ms
80,732 KB |
testcase_19 | AC | 1,367 ms
86,868 KB |
testcase_20 | AC | 905 ms
78,200 KB |
testcase_21 | AC | 1,504 ms
89,660 KB |
testcase_22 | AC | 519 ms
68,492 KB |
testcase_23 | AC | 254 ms
56,648 KB |
ソースコード
import java.io.*; import java.util.*; public class Main_yukicoder130_1 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); Printer pr = new Printer(System.out); int n = sc.nextInt(); SortedSet<Integer> a = new TreeSet<>(); for (int i = 0; i < n; i++) { a.add(sc.nextInt()); } pr.println(rec(0, 0, 0, a)); pr.close(); sc.close(); } private static int rec(int mask, int bit, int max, SortedSet<Integer> a) { if (mask == 0x7fffffff) { return max; } int nmask = mask >>> 1 | 0x40000000; int nbit = ((~mask & 0x7fffffff) + 1) >>> 1; int to1 = (~nmask & 0x7fffffff | bit) + 1; int to2 = (~nmask & 0x7fffffff | bit | nbit) + 1; if (to1 < 0) { to1 = Integer.MAX_VALUE; } if (to2 < 0) { to2 = Integer.MAX_VALUE; } SortedSet<Integer> a1 = a.subSet(bit, to1); SortedSet<Integer> a2 = a.subSet(bit | nbit, to2); if (a1.size() == 0 && a2.size() == 0) { return Integer.MAX_VALUE; } else if (a2.size() == 0) { return rec(nmask, bit, max, a); } else if (a1.size() == 0) { return rec(nmask, bit | nbit, max, a); } else { return Math.min(rec(nmask, bit, max | nbit, a), rec(nmask, bit | nbit, max | nbit, a)); } } @SuppressWarnings("unused") private static class Scanner { BufferedReader br; Iterator<String> it; Scanner (InputStream in) { br = new BufferedReader(new InputStreamReader(in)); } String next() throws RuntimeException { try { if (it == null || !it.hasNext()) { it = Arrays.asList(br.readLine().split(" ")).iterator(); } return it.next(); } catch (IOException e) { throw new IllegalStateException(); } } int nextInt() throws RuntimeException { return Integer.parseInt(next()); } long nextLong() throws RuntimeException { return Long.parseLong(next()); } float nextFloat() throws RuntimeException { return Float.parseFloat(next()); } double nextDouble() throws RuntimeException { return Double.parseDouble(next()); } void close() { try { br.close(); } catch (IOException e) { // throw new IllegalStateException(); } } } private static class Printer extends PrintWriter { Printer(PrintStream out) { super(out); } } }