結果
問題 | No.130 XOR Minimax |
ユーザー | threepipes_s |
提出日時 | 2015-01-17 15:25:09 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 830 ms / 5,000 ms |
コード長 | 3,709 bytes |
コンパイル時間 | 2,414 ms |
コンパイル使用メモリ | 79,712 KB |
実行使用メモリ | 72,888 KB |
最終ジャッジ日時 | 2024-09-12 22:33:34 |
合計ジャッジ時間 | 12,172 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 284 ms
63,952 KB |
testcase_01 | AC | 53 ms
50,404 KB |
testcase_02 | AC | 53 ms
50,344 KB |
testcase_03 | AC | 54 ms
50,548 KB |
testcase_04 | AC | 425 ms
65,424 KB |
testcase_05 | AC | 830 ms
72,888 KB |
testcase_06 | AC | 726 ms
69,660 KB |
testcase_07 | AC | 702 ms
68,028 KB |
testcase_08 | AC | 501 ms
67,520 KB |
testcase_09 | AC | 166 ms
58,324 KB |
testcase_10 | AC | 229 ms
60,596 KB |
testcase_11 | AC | 642 ms
67,272 KB |
testcase_12 | AC | 143 ms
55,732 KB |
testcase_13 | AC | 525 ms
66,744 KB |
testcase_14 | AC | 512 ms
66,824 KB |
testcase_15 | AC | 69 ms
50,928 KB |
testcase_16 | AC | 368 ms
65,272 KB |
testcase_17 | AC | 357 ms
65,288 KB |
testcase_18 | AC | 405 ms
65,428 KB |
testcase_19 | AC | 408 ms
66,948 KB |
testcase_20 | AC | 249 ms
60,668 KB |
testcase_21 | AC | 422 ms
66,868 KB |
testcase_22 | AC | 187 ms
58,600 KB |
testcase_23 | AC | 116 ms
54,812 KB |
ソースコード
import java.io.BufferedReader; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Comparator; import java.util.LinkedList; import java.util.List; import java.util.Queue; public class Main { public static void main(String[] args) throws NumberFormatException, IOException{ ContestScanner in = new ContestScanner(); int n = in.nextInt(); Queue<Long> a = new LinkedList<Long>(); for(int i=0; i<n; i++){ a.add(in.nextLong()); } System.out.println(minimax(30, a)); } // d bit目より上のbitが0のときに集合sに対する題意にそった値を返す public static long minimax(int d, Queue<Long> s){ if(d == 0 || s.size() <= 1) return 0; long mask = 1 << (d-1); Queue<Long> s1 = new LinkedList<Long>(); Queue<Long> s2 = new LinkedList<Long>(); while(!s.isEmpty()){ long val = s.poll(); if((mask & val) == 0){ s1.add(val); }else{ s2.add(val); } } if(s1.size() == 0){ return ~mask & minimax(d-1, s2); }else if(s2.size() == 0){ return minimax(d-1, s1); }else{ return Math.min(mask | minimax(d-1, s1), mask | minimax(d-1, s2)); } } } class MyComp implements Comparator<int[]>{ public int compare(int[] a, int[] b) { return a[0] - b[0]; } } // //class Reverse implements Comparator<Integer>{ // public int compare(Integer arg0, Integer arg1) { // return arg1 - arg0; // } //} class Node implements Comparable<Node>{ int id; int qNum; int xor; List<Node> edge = new ArrayList<Node>(); public Node(int id, int q, int xor){ this.id = id; qNum = q; this.xor = xor; } public void createEdge(Node node){ edge.add(node); } @Override public int compareTo(Node n) { return n.qNum - qNum; } } class MyMath{ public final static double PIhalf = Math.PI/2.0; public static double pAngle(double x, double y){ // ベクトル(1, 0)と(x, y)とのなす角を返す(rad:0 to 2pi) if(x == 0){ if(y == 0){ System.err.println("pAngle error: zero vector."); return 0; }else if(y < 0){ return PIhalf*3.0; }else{ return PIhalf; } } double rad = Math.atan(y/x); if(rad < 0){ rad += Math.PI*2.0; } return rad; } public static long fact(long n){ long res = 1; while(n > 0){ res *= n--; } return res; } public static long[][] pascalT(int n){ long[][] tri = new long[n][]; for(int i=0; i<n; i++){ tri[i] = new long[i+1]; for(int j=0; j<i+1; j++){ if(j == 0 || j == i){ tri[i][j] = 1; }else{ tri[i][j] = tri[i-1][j-1] + tri[i-1][j]; } } } return tri; } // 最大公約数 static int gcd(int a, int b){ return b == 0 ? a : gcd(b, a % b); } // 最小公倍数 static int lcm(int a, int b){ return a * b / gcd(a, b); } } class ContestScanner{ private BufferedReader reader; private String[] line; private int idx; public ContestScanner() throws FileNotFoundException{ reader = new BufferedReader(new InputStreamReader(System.in)); } public ContestScanner(String filename) throws FileNotFoundException{ reader = new BufferedReader(new InputStreamReader(new FileInputStream(filename))); } public String nextToken() throws IOException{ if(line == null || line.length <= idx){ line = reader.readLine().trim().split(" "); idx = 0; } return line[idx++]; } public long nextLong() throws IOException, NumberFormatException{ return Long.parseLong(nextToken()); } public int nextInt() throws NumberFormatException, IOException{ return (int)nextLong(); } public double nextDouble() throws NumberFormatException, IOException{ return Double.parseDouble(nextToken()); } }