oj.uz

Submission #1090198

# Submission time Handle Problem Language Result Execution time Memory
1090198 2024-09-18T00:51:05 Z TrinhKhanhDung XOR Sum (info1cup17_xorsum) C++14
100 / 100
 654 ms 31476 KB 
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define sz(x) (int)x.size()
#define ALL(v) v.begin(),v.end()
#define MASK(k) (1LL << (k))
#define BIT(x, i) (((x) >> (i)) & 1)
#define oo (ll)1e18
#define INF (ll)1e9
#define MOD (ll)(1e9 + 7)

using namespace std;

template<class T1, class T2>
    bool maximize(T1 &a, T2 b){if(a < b){a = b; return true;} return false;}

template<class T1, class T2>
    bool minimize(T1 &a, T2 b){if(a > b){a = b; return true;} return false;}

template<class T1, class T2>
    void add(T1 &a, T2 b){a += b; if(a >= MOD) a -= MOD;}

template<class T1, class T2>
    void sub(T1 &a, T2 b){a -= b; if(a < 0) a += MOD;}

template<class T>
    void cps(T &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}

const int MAX = 1e6 + 10;

int N;
int a[MAX];

void solve(){
    cin >> N;
    for(int i = 1; i <= N; i++) cin >> a[i];

    int ans = 0;
    for(int j = 0; j < 30; j++){
        vector<vector<int>> pre(2, vector<int>(N + 3, 0));
        for(int i = 1; i <= N; i++){
            pre[0][i] = pre[0][i - 1];
            pre[1][i] = pre[1][i - 1];
            pre[BIT(a[i], j)][i]++;
        }

        ll sum = 0;
        int k = 1;
        for(int i = N; i >= 1; i--){
            int cur = (MASK(j) - 1) & a[i];
            minimize(k, i);
            while(k <= i && ((MASK(j) - 1) & a[k]) + cur < MASK(j)) k++;
            int b = BIT(a[i], j);
            sum += (pre[!b][k - 1]) + (pre[b][i] - pre[b][k - 1]);
        }

        vector<int> t[2];
        for(int i = 1; i <= N; i++){
            t[BIT(a[i], j)].push_back(a[i]);
        }

        for(int i = 1; i <= sz(t[0]); i++){
            a[i] = t[0][i - 1];
        }
        for(int i = sz(t[0]) + 1; i <= N; i++){
            a[i] = t[1][i - sz(t[0]) - 1];
        }

        if(sum & 1) ans += MASK(j);
    }

    cout << ans << '\n';
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    //i freopen("order.inp","r",stdin);
    // freopen("order.out","w",stdout);

    solve();

    return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 2 ms 604 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 502 ms 26812 KB Output is correct
2 Correct 484 ms 25064 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 502 ms 26812 KB Output is correct
2 Correct 484 ms 25064 KB Output is correct
3 Correct 539 ms 28832 KB Output is correct
4 Correct 553 ms 27916 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 68 ms 3608 KB Output is correct
4 Correct 61 ms 3564 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 502 ms 26812 KB Output is correct
4 Correct 484 ms 25064 KB Output is correct
5 Correct 539 ms 28832 KB Output is correct
6 Correct 553 ms 27916 KB Output is correct
7 Correct 68 ms 3608 KB Output is correct
8 Correct 61 ms 3564 KB Output is correct
9 Correct 654 ms 31476 KB Output is correct
10 Correct 650 ms 31268 KB Output is correct
11 Correct 635 ms 31416 KB Output is correct