結果

問題 No.183 たのしい排他的論理和(EASY)
コンテスト
ユーザー @abcde
提出日時 2019-04-29 09:09:08
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 21 ms / 5,000 ms
コード長 1,382 bytes
コンパイル時間 1,629 ms
コンパイル使用メモリ 168,664 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-01 23:19:05
合計ジャッジ時間 2,522 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

// 以下の問題を参考に対応.
// No.4 おもりと天秤
// https://yukicoder.me/problems/no/4
#include <bits/stdc++.h>
using namespace std;

// 作成可能な整数のリストを更新する.
// @param m: 整数のリスト.
// @param n: 追加する整数.
// @return ret: 更新した作成可能な整数のリスト.
map<int, int> updateIntegers(map<int, int> m, int n){
    map<int, int> ret;
    for(auto &p : m) ret[p.first]++, ret[(p.first ^ n)]++;
    // for(auto &p : ret) cout << "updateIntegers(ret): " << p.first << " ";
    // cout << endl;
    return ret;
}

int main() {
    
    // 1. 入力情報取得.
    int N;
    cin >> N;
    
    // 2. 入力データから作成可能な整数のリストを更新していく.
    int A[N];
    cin >> A[0];
    map<int, int> ans;
    ans[0]++, ans[A[0]]++;
    for(int i = 1; i < N; i++){
        cin >> A[i];
        if(ans[A[i]] == 0){
            map<int, int> lm = updateIntegers(ans, A[i]);
            swap(ans, lm);
        }
    }
    // for(auto &p : ans) cout << p.first << " ";
    // cout << endl;
    
    // 3. 出力 ～ 後処理.
    // ex.
    // 5
    // 1 7 101 212 333
    // -> 32 で OK ???.
    // 0 1 6 7 98 99 100 101 176 177 182 183 210 211 212 
    // 213 296 297 302 303 330 331 332 333 408 409 414 415 506 507 
    // 508 509
    cout << ans.size() << endl;
    return 0;
    
}
0