제출 #1140909

#제출 시각아이디문제언어결과실행 시간메모리
1140909__Davit__XOR Sum (info1cup17_xorsum)C++17
100 / 100
854 ms34180 KiB
#include<bits/stdc++.h> #define ll long long #define lld long double #define ff first #define ss second #define pb push_back #define mp make_pair #define vr(v) v.begin(),v.end() #define rv(v) v.rbegin(),v.rend() #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; typedef tree<pair<int, int>, null_type, less<pair<int, int> >, rb_tree_tag, tree_order_statistics_node_update> ordered_set; //#include "algo/debug.h" void solve() { int n; cin >> n; vector<ll> v(n); ll answer = 0; for (int i = 0; i < n; i++)cin >> v[i]; vector<ll> a; auto f = [&](ll x)-> ll { //the number of pairs whose sum does not exceed x ll res = 0; int it = n - 1; for (int i = 0; i < n; i++) { while (it >= i && a[i] + a[it] > x) { it--; } if (it < i)break; res += it - i + 1; } return res; }; for (int i = 0; i < 31; i++) { //radix sort vector<ll> zro, mek; for (int j = 0; j < n; j++) { if ((v[j] >> i) & 1)mek.pb(v[j]); else zro.pb(v[j]); } v.clear(); for (int j = 0; j < (int) zro.size(); j++)v.pb(zro[j]); for (int j = 0; j < (int) mek.size(); j++)v.pb(mek[j]); a.clear(); // for (int j = 0; j < n; j++)a.pb(v[j] % (1ll << (i + 1))); for (int j = 0; j < n; j++)a.pb(v[j] & ((1ll << (i + 1)) - 1)); ll val = f((1ll << (i + 1)) - 1) - f((1ll << (i)) - 1); val += f((1ll << (i + 2)) - 2) - f((1ll << (i + 1)) + (1ll << (i)) - 1); if (val & 1)answer += (1ll << i); } cout << answer << endl; } int main() { int t = 1; // cin >> t; while (t--)solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...