#367585 (C++14) No.862 XORでX

• 問題: No.862 XORでX
• ユーザー: mamekin
• 提出日時: 2019-08-10 19:28:54
• 言語: C++14 (gcc 15.2.0 + boost 1.89.0)
• 結果: CE (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 2,365 bytes
• コンパイル時間: 989 ms
• コンパイル使用メモリ: 129,744 KB
• 最終ジャッジ日時: 2026-04-02 17:37:55
• 合計ジャッジ時間: 6,817 ms
• ジャッジサーバーID （参考情報）: judge4_0 / judge5_0

コンパイルメッセージ

main.cpp:32:5: error: 'uint32_t' does not name a type
   32 |     uint32_t x, y, z, w;
      |     ^~~~~~~~
main.cpp:27:1: note: 'uint32_t' is defined in header '<cstdint>'; this is probably fixable by adding '#include <cstdint>'
   26 | #include <regex>
  +++ |+#include <cstdint>
   27 | using namespace std;
main.cpp:34:22: error: expected ')' before 'seed'
   34 |     Xorshift(uint32_t seed=88675123, int32_t loop=50){
      |             ~        ^~~~~
      |                      )
main.cpp:43:5: error: 'uint32_t' does not name a type
   43 |     uint32_t operator()(){
      |     ^~~~~~~~
main.cpp:43:5: note: 'uint32_t' is defined in header '<cstdint>'; this is probably fixable by adding '#include <cstdint>'
main.cpp:48:5: error: 'uint32_t' does not name a type
   48 |     uint32_t operator()(uint32_t size){
      |     ^~~~~~~~
main.cpp:48:5: note: 'uint32_t' is defined in header '<cstdint>'; this is probably fixable by adding '#include <cstdint>'
main.cpp:51:5: error: 'uint64_t' does not name a type
   51 |     uint64_t get64(){
      |     ^~~~~~~~
main.cpp:51:5: note: 'uint64_t' is defined in header '<cstdint>'; this is probably fixable by adding '#include <cstdint>'
main.cpp:56:5: error: 'uint64_t' does not name a type
   56 |     uint64_t get64(uint64_t size){
      |     ^~~~~~~~
main.cpp:56:5: note: 'uint64_t' is defined in header '<cstdint>'; this is probably fixable by adding '#include <cstdint>'
main.cpp: In member function 'void Xorshift::shuffle(std::vector<_Tp>&)':
main.cpp:61:9: error: 'uint32_t' was not declared in this scope [-Wtemplate-body]
   61 |         uint32_t n = v.size();
      |         ^~~~~~~~
main.cpp:61:9: note: 'uint32_t' is defined in header '<cstdint>'; this is probably fixable by adding '#include <cstdint>'
main.cpp:62:22: error: expected ';' before 'i' [-Wtemplate-body]
   62 |         for(uint32_t i=0; i<n-1; ++i){
      |                      ^
main.cpp:62:27: error: 'i' was not declared in this scope [-Wtemplate-body]
   62

ソースコード

#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;
}