結果

問題 No.130 XOR Minimax
ユーザー kurenai3110
提出日時 2017-04-04 04:40:47
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 249 ms / 5,000 ms
コード長 1,582 bytes
コンパイル時間 964 ms
コンパイル使用メモリ 66,376 KB
実行使用メモリ 61,696 KB
最終ジャッジ日時 2024-09-12 22:44:54
合計ジャッジ時間 4,839 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
struct Trie {
    Trie *next[2];
    Trie() {
        fill(next, next + 2, (Trie *)0);
    }
    void insert(const char *s) {
        if (*s == '\0') return;
        if (this->next[*s-'0'] == NULL)
            this->next[*s-'0'] = new Trie();
        this->next[*s-'0']->insert(s + 1);
    }
    bool find(const char *s) {
        if (*s == '\0') return true;
        if (this->next[*s-'0'] == NULL)
            return false;
        return this->next[*s-'0']->find(s + 1);
    }
};
string binary(int a, int l = 32) {
    string s = "";
    for (int i = 0; i < l; i++) {
        s += to_string(a & 1);
        a >>= 1;
    }
    reverse(s.begin(), s.end());
    return s;
}
int binary_to_int(string bi) {
    int a = 0;
    for (int i = 0; i < bi.size(); i++) {
        a += (bi[bi.size() - 1 - i] - '0') << i;
    }
    return a;
}
string solve(Trie* trie) {
    bool exist0 = trie->find("0"), exist1 = trie->find("1");
    string bi = "";
    if (exist0 && !exist1)bi = "0" + solve(trie->next[0]);
    else if(!exist0 && exist1)bi = "0" + solve(trie->next[1]);
    else if (!exist0 && !exist1)return bi;
    else {
        string next_bi0 = "1" + solve(trie->next[0]);
        string next_bi1 = "1" + solve(trie->next[1]);
        if (binary_to_int(next_bi0) < binary_to_int(next_bi1))bi = next_bi0;
        else bi = next_bi1;
    }
    return bi;
}
int main()
{
    int n; cin >> n;
    vector<string>binaryA(n);
    for (int i = 0; i < n; i++) {
        int a; cin >> a;
        binaryA[i] = binary(a);
    }
    Trie* trie = new Trie();
    for (int i = 0; i < n; i++) {
        trie->insert(binaryA[i].data());
    }
    cout << binary_to_int(solve(trie)) << endl;
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0