#97823 (Java) No.130 XOR Minimax

• 問題: No.130 XOR Minimax
• ユーザー: Grenache
• 提出日時: 2016-06-15 19:24:50
• 言語: Java (openjdk 23)
• 結果: AC
• 実行時間: 1,572 ms / 5,000 ms
• コード長: 2,328 bytes
• コンパイル時間: 4,361 ms
• コンパイル使用メモリ: 80,352 KB
• 実行使用メモリ: 89,300 KB
• 最終ジャッジ日時: 2024-09-12 22:41:55
• 合計ジャッジ時間: 21,928 ms
• ジャッジサーバーID （参考情報）: judge2 / judge3

ファイルパターン	結果
sample	AC * 3
other	AC * 21

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
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);
        }
    }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX