結果

問題 No.862 XORでX
コンテスト
ユーザー mamekin
提出日時 2019-08-10 19:28:54
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 127 ms / 2,000 ms
コード長 2,365 bytes
コンパイル時間 1,152 ms
コンパイル使用メモリ 123,224 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-19 17:20:36
合計ジャッジ時間 5,003 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
#include <memory>
#include <regex>
using namespace std;

class Xorshift
{
private:
    uint32_t x, y, z, w;
public:
    Xorshift(uint32_t seed=88675123, int32_t loop=50){
        x = 123456789;
        y = 362436069;
        z = 521288629;
        w = seed;
        while(--loop >= 0){
            (*this)();
        }
    }
    uint32_t operator()(){
        uint32_t t=(x^(x<<11));
        x=y; y=z; z=w;
        return w=(w^(w>>19))^(t^(t>>8));
    }
    uint32_t operator()(uint32_t size){
        return (*this)() % size;
    }
    uint64_t get64(){
        uint64_t a = (*this)();
        uint64_t b = (*this)();
        return (a << 32) | b;
    }
    uint64_t get64(uint64_t size){
        return get64() % size;
    }
    template <class T>
    void shuffle(vector<T>& v){
        uint32_t n = v.size();
        for(uint32_t i=0; i<n-1; ++i){
            uint32_t j = (*this)(n-i) + i;
            swap(v[i], v[j]);
        }
    }
};
Xorshift xorshift;

const int MAX = 100005;

void solve(int n, int x, vector<bool>& ans)
{
    if(n > MAX / 2){
        int y = x;
        for(int i=1; i<=MAX; ++i)
            y ^= i;
        solve(MAX - n, y, ans);
        for(int i=1; i<=MAX; ++i)
            ans[i] = !ans[i];
        return;
    }

    ans.assign(MAX+1, false);
    if(n == 1){
        ans[x] = true;
        return;
    }

    vector<int> v(MAX);
    for(int i=0; i<MAX; ++i)
        v[i] = i + 1;

    for(;;){
        xorshift.shuffle(v);
        int y = x;
        for(int i=0; i<n-1; ++i)
            y ^= v[i];
        if(find(v.begin() + n - 1, v.end(), y) != v.end()){
            v[n-1] = y;
            for(int i=0; i<n; ++i)
                ans[v[i]] = true;
            return;
        }
    }
}

int main()
{
    int n, x;
    cin >> n >> x;

    vector<bool> ans;
    solve(n, x, ans);
    for(int i=1; i<=MAX; ++i){
        if(ans[i])
            cout << i << endl;
    }

    return 0;
}
0