Submission #1201834

#TimeUsernameProblemLanguageResultExecution timeMemory
1201834M_SH_OXOR Sum (info1cup17_xorsum)C++20
100 / 100
1089 ms56928 KiB
#include <bits/stdc++.h> /*#include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp>*/ #define ll long long #define ll1 long long #define ull unsigned long long #define dou long double #define str string #define vll vector<ll> #define vi vector<int> #define pll pair<ll, ll> #define vpll vector<pll> #define vbool vector<bool> #define vstr vector<str> #define vvll vector<vll> #define pb push_back #define pf push_front //#define endl "\n" #define fr first #define se second // #define sortcmp(a) sort(a.begin(), a.end(), cmp) #define sort(a) sort(a.begin(), a.end()) #define reverse(a) reverse(a.begin(), a.end()) #define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define INF 5000000000000000000 #define ordered_set tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> using namespace std; //using namespace __gnu_pbds; mt19937 rng(time(0)); ll randll(ll l, ll r){ return uniform_int_distribution<ll>(l, r)(rng); } int main() { ll n; cin >> n; vll a(n); for (int i = 0; i < n; i ++) { cin >> a[i]; } ll res = 0; vpll v(n); for (int i = 0; i < n; i ++) { v[i] = {0, i}; } for (int i = 0; i < 30; i ++) { vll b, b1, bp, bp1; ll k = 0; for (int j = 0; j < n; j ++) { //cout << v[j].fr << ' '; if (a[v[j].se] & (1 << i)) { b1.pb(a[v[j].se] & ((1 << i)-1)); bp1.pb(v[j].se); } else { b.pb(v[j].fr); bp.pb(v[j].se); } } //cout << endl; ll l = b.size()-1, l1 = b1.size()-1; for (int j = 0; j < b.size(); j ++) { if ((b[j]+b[j]) >= (1 << i)) k ++; while (l >= 0) { if (b[l]+b[j] >= (1 << i)) l --; else break; } while (l1 >= 0) { if (b1[l1]+b[j] >= (1 << i)) l1 --; else break; } k += b.size()-l-1 + l1+1; } l = b.size()-1, l1 = b1.size()-1; for (int j = 0; j < b1.size(); j ++) { if ((b1[j]+b1[j]) >= (1 << i)) k ++; while (l >= 0) { if (b[l]+b1[j] >= (1 << i)) l --; else break; } while (l1 >= 0) { if (b1[l1]+b1[j] >= (1 << i)) l1 --; else break; } k += b1.size()-l1-1 + l+1; } /*cout << k << endl; //if (i != 1) continue; for (int j : b) { cout << j << ' '; } cout << endl; for (int j : b1) { cout << j << ' '; } cout << endl;*/ if (k/2 % 2) res += (1 << i); l = 0, l1 = 0; for (int i1 = 0; i1 < n; i1++) { //cout << l << ' ' << l1 << endl; if (l < b.size()) { v[i1] = {b[l], bp[l]}; l ++; } else { v[i1] = {b1[l1] + (1 << i), bp1[l1]}; l1 ++; } } } cout << res << endl; }
#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...