oj.uz

Submission #886505

# Submission time Handle Problem Language Result Execution time Memory
886505 2023-12-12T09:07:54 Z AnhPham XOR Sum (info1cup17_xorsum) C++17
0 / 100
 1 ms 348 KB 
#include <bits/stdc++.h>

#ifdef OP_DEBUG
    #include <algo/debug.h>
#else
    #define debug(...) 26
#endif

using namespace std;

#define int 	long long // maybe tle?
#define sz(v)   (int)(v).size()
#define all(v)  (v).begin(), (v).end()
#define TcT     template <class T

const   int     MOD = (int)1e9 + 7, INF = (int)2e9 + 9, INF64 = (int)4e18 + 18;

TcT>            bool minimize(T &lhs, const T &rhs) { return rhs < lhs ? lhs = rhs, 1 : 0; }
TcT>            bool maximize(T &lhs, const T &rhs) { return rhs > lhs ? lhs = rhs, 1 : 0; }

TcT, class S>   istream &operator >> (istream &scanf, pair <T, S> &u) { return scanf >> u.first >> u.second;        }
TcT, class S>   ostream &operator << (ostream &print, pair <T, S> &u) { return print << u.first << ' ' << u.second; }

void solve();

int32_t main() {
    freopen("input.inp", "r", stdin);
    freopen("B.out", "w", stdout);

    cin.tie(nullptr), cout.tie(nullptr) -> sync_with_stdio(0);
    int testcases = 1;

#define TC 0
    if (TC) { cin >> testcases; } for (; testcases--;) { solve(); }
}

/* [Pham Hung Anh - 11I - Tran Hung Dao High School for Gifted Student] */

const int N = 3e5 + 5;

int n;
int a[N];

int check(int bit) {
    int cnt = 0;
    vector <int> rems;
    for (int i = 1; i <= n; ++i) {
        if ((a[i] & (1 << bit)) != 0)
            ++cnt;
        
        rems.push_back((a[i] % (1 << bit)));
    }

    sort(all(rems));

    int ans = (cnt * (n - cnt)) % 2;
    int r = n - 1;
    for (int l = 0; l < n; ++l) {
        if (l > r)
            ++r;
 
        while (r > l && rems[l] + rems[r - 1] >= (1 << bit))
            --r;
 
        if (rems[l] + rems[r] >= (1 << bit))
            ans = (ans + n - r) % 2;
    }

    return ans;
}

void solve() {
    cin >> n;

    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    
    int ans = 0;
    for (int i = 0; i <= 29; ++i)
        if (check(i))
            ans |= (1 << i);
    
    cout << ans << '\n';
}

Compilation message

xorsum.cpp: In function 'int32_t main()':
xorsum.cpp:27:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |     freopen("input.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
xorsum.cpp:28:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |     freopen("B.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 21.0

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

Subtask #4
0 / 38.0

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

Subtask #5
0 / 23.0

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