test/aoj0402.test.cpp

• View this file on GitHub
• Last update: 2021-06-21 15:24:20+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0402

Depends on

• math/fwht.cpp

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0402"
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using uint = unsigned;
using ull = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

#include "../math/fwht.cpp"

int main() {
    int n; ll k;
    cin >> n >> k;
    int S = 0;
    vector<ll> A(1<<20);
    A[0] = 1;
    for (int i = 0; i < n; ++i) {
        int x; scanf("%d", &x);
        S ^= x;
        A[S]++;
    }
    fwht(A);
    for (int i = 0; i < 1<<20; ++i) A[i] *= A[i];
    ifwht(A);
    for (int i = (1<<20) - 1; i >= 0; --i) {
        k -= A[i]/2;
        if(k <= 0){
            cout << i << "\n";
            return 0;
        }
    }
    return 0;
}

#line 1 "test/aoj0402.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0402"
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using uint = unsigned;
using ull = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

#line 1 "math/fwht.cpp"
template<class T>
void fwht(vector<T> &v){
    int sz = 1;
    while(sz < v.size()) sz <<= 1;
    v.resize(sz);
    for (int i = 1; i < sz; i <<= 1) {
        for (int j = 0; j < sz; j += (i<<1)) {
            for (int k = 0; k < i; ++k) {
                T x = v[j+k], y = v[j+k+i];
                v[j+k] = (x+y), v[j+k+i] = (x-y);
            }
        }
    }
}

template<class T>
void ifwht(vector<T> &v){
    int sz = 1;
    while(sz < v.size()) sz <<= 1;
    v.resize(sz);
    for (int i = 1; i < sz; i <<= 1) {
        for (int j = 0; j < sz; j += (i<<1)) {
            for (int k = 0; k < i; ++k) {
                T x = v[j+k], y = v[j+k+i];
                v[j+k] = (x+y)>>1, v[j+k+i] = (x-y)>>1;
            }
        }
    }
}
#line 21 "test/aoj0402.test.cpp"

int main() {
    int n; ll k;
    cin >> n >> k;
    int S = 0;
    vector<ll> A(1<<20);
    A[0] = 1;
    for (int i = 0; i < n; ++i) {
        int x; scanf("%d", &x);
        S ^= x;
        A[S]++;
    }
    fwht(A);
    for (int i = 0; i < 1<<20; ++i) A[i] *= A[i];
    ifwht(A);
    for (int i = (1<<20) - 1; i >= 0; --i) {
        k -= A[i]/2;
        if(k <= 0){
            cout << i << "\n";
            return 0;
        }
    }
    return 0;
}

Back to top page