oj.uz

답안 #1009466

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1009466 2024-06-27T14:42:48 Z windowwife XOR Sum (info1cup17_xorsum) C++17
100 / 100
 580 ms 44356 KB 
#include<bits/stdc++.h>
#define ll long long
#define task " "
using namespace std;
const int maxn = 1e6 + 1, mod = 1e9 + 7;
ll n, a[maxn], m[maxn], id[maxn], cnt = 0, idx = 0, res = 0;
int t, p, q, r;
vector<int> v[2];
int main ()
{
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        m[i] = 0;
        id[i] = i;
    }
    m[n + 1] = (1LL << 32);
    for (int j = 0; j <= 30; j++)
    {
        cnt = idx = 0; v[0].clear(); v[1].clear();
        for (int i = 1; i <= n; i++)
            v[(a[id[i]] >> j) & 1].push_back(id[i]);
        for (int i : v[0])
        {
            m[++idx] = a[i] & ((1 << (j + 1)) - 1);
            id[idx] = i;
        }
        for (int i : v[1])
        {
            m[++idx] = a[i] & ((1 << (j + 1)) - 1);
            id[idx] = i;
        }
        t = p = q = r = n + 1;
        for (int i = 1; i <= n; i++)
        {
            while (t > 1 && m[t - 1] >= (1LL << (j + 1)) - m[i]) t--;
            while (p > 1 && m[p - 1] >= (1LL << j) - m[i]) p--;
            while (q > 1 && m[q - 1] >= (1LL << (j + 2)) - m[i]) q--;
            while (r > 1 && m[r - 1] >= (1LL << j) + (1LL << (j + 1)) - m[i]) r--;
            cnt += (min(t, i + 1) - min(p, i + 1)) + (min(q, i + 1) - min(r, i + 1));
            //cnt += lower_bound(m + 1, m + i + 1, (1LL << (j + 1)) - m[i]) - lower_bound(m + 1, m + i + 1, (1LL << j) - m[i]);
            //cnt += lower_bound(m + 1, m + i + 1, (1LL << (j + 2)) - m[i]) - lower_bound(m + 1, m + i + 1, (1LL << j) + (1LL << (j + 1)) - m[i]);
        }
        res += (cnt % 2)*(1LL << j);
    }
    cout << res;
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4444 KB Output is correct
2 Correct 3 ms 4444 KB Output is correct

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 347 ms 40328 KB Output is correct
2 Correct 322 ms 38208 KB Output is correct

Subtask #3
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 347 ms 40328 KB Output is correct
2 Correct 322 ms 38208 KB Output is correct
3 Correct 400 ms 40256 KB Output is correct
4 Correct 381 ms 42108 KB Output is correct

Subtask #4
38.0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4444 KB Output is correct
2 Correct 3 ms 4444 KB Output is correct
3 Correct 58 ms 9804 KB Output is correct
4 Correct 58 ms 10832 KB Output is correct

Subtask #5
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4444 KB Output is correct
2 Correct 3 ms 4444 KB Output is correct
3 Correct 347 ms 40328 KB Output is correct
4 Correct 322 ms 38208 KB Output is correct
5 Correct 400 ms 40256 KB Output is correct
6 Correct 381 ms 42108 KB Output is correct
7 Correct 58 ms 9804 KB Output is correct
8 Correct 58 ms 10832 KB Output is correct
9 Correct 580 ms 43764 KB Output is correct
10 Correct 561 ms 42816 KB Output is correct
11 Correct 533 ms 44356 KB Output is correct