結果
問題 | No.130 XOR Minimax |
ユーザー | htensai |
提出日時 | 2020-01-15 15:43:55 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 1,932 ms / 5,000 ms |
コード長 | 1,482 bytes |
コンパイル時間 | 3,044 ms |
コンパイル使用メモリ | 75,324 KB |
実行使用メモリ | 101,248 KB |
最終ジャッジ日時 | 2023-10-10 00:27:42 |
合計ジャッジ時間 | 28,384 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 996 ms
83,152 KB |
testcase_01 | AC | 116 ms
55,664 KB |
testcase_02 | AC | 113 ms
55,600 KB |
testcase_03 | AC | 115 ms
55,588 KB |
testcase_04 | AC | 399 ms
60,464 KB |
testcase_05 | AC | 548 ms
60,636 KB |
testcase_06 | AC | 1,065 ms
88,892 KB |
testcase_07 | AC | 1,688 ms
99,312 KB |
testcase_08 | AC | 1,904 ms
101,248 KB |
testcase_09 | AC | 390 ms
64,728 KB |
testcase_10 | AC | 466 ms
68,452 KB |
testcase_11 | AC | 871 ms
76,692 KB |
testcase_12 | AC | 293 ms
61,208 KB |
testcase_13 | AC | 749 ms
75,120 KB |
testcase_14 | AC | 1,549 ms
97,068 KB |
testcase_15 | AC | 190 ms
59,720 KB |
testcase_16 | AC | 1,166 ms
91,180 KB |
testcase_17 | AC | 1,356 ms
90,912 KB |
testcase_18 | AC | 1,417 ms
89,284 KB |
testcase_19 | AC | 1,671 ms
93,036 KB |
testcase_20 | AC | 939 ms
80,816 KB |
testcase_21 | AC | 1,932 ms
96,460 KB |
testcase_22 | AC | 642 ms
70,260 KB |
testcase_23 | AC | 357 ms
60,952 KB |
ソースコード
import java.util.*; public class Main { static int[] base; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); base = new int[31]; base[0] = 1; for (int i = 1; i < base.length; i++) { base[i] = base[i - 1] * 2; } HashSet<Integer> set = new HashSet<>(); for (int i = 0; i < n; i++) { set.add(sc.nextInt()); } System.out.println(getMin(30, set)); } static int getMin(int idx, HashSet<Integer> set) { if (idx == 0) { if(set.size() == 1) { return 0; } else { return 1; } } HashSet<Integer> next = new HashSet<>(); for (int x : set) { if (x >= base[idx]) { next.add(x); } } if (next.size() == 0) { return getMin(idx - 1, set); } else if (next.size() == set.size()) { HashSet<Integer> tmp = new HashSet<>(); for (int x : next) { tmp.add(x - base[idx]); } return getMin(idx - 1, tmp); } else { HashSet<Integer> tmp = new HashSet<>(); for (int x : next) { tmp.add(x - base[idx]); set.remove(x); } return base[idx] + Math.min(getMin(idx - 1, set), getMin(idx - 1, tmp)); } } }