oj.uz

Submission #889393

# Submission time Handle Problem Language Result Execution time Memory
889393 2023-12-19T15:47:09 Z boris_mihov XOR Sum (info1cup17_xorsum) C++17
0 / 100
 1600 ms 23888 KB 
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 1000000 + 10;
const int MAXLOG = 31;

int n;
int cnt[2];
llong a[MAXN];
llong b[MAXN];
llong c[MAXN];
llong answer;

void solve()
{
    for (int bit = 0 ; bit < MAXLOG ; ++bit)
    {
        int cntOnes = 0;
        std::iota(c + 1, c + 1 + n, 1);
        std::sort(c + 1, c + 1 + n, [&](int x, int y)
        {
            return b[x] < b[y];
        });

        int ptr = n + 1;
        llong count = 1LL * cntOnes * (n - cntOnes);
        for (int i = 1 ; i <= n ; ++i)
        {
            while (ptr > 1 && b[c[ptr - 1]] + b[c[i]] >= (1 << bit))
            {
                ptr--;
            }

            count += n + 1 - ptr;
        }

        if (count & 1)
        {
            answer |= (1 << bit);
        }
    
        for (int i = 1 ; i <= n ; ++i)
        {
            b[i] |= (a[i] & (1 << bit));
            cntOnes += ((a[i] & (1 << bit)) > 0);
        }
    }

    std::cout << answer << '\n';
}

void input()
{
    std::cin >> n;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> a[i];
    }
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}  

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1636 ms 23888 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1636 ms 23888 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -