Submission #767640

#TimeUsernameProblemLanguageResultExecution timeMemory
767640fanwenXOR Sum (info1cup17_xorsum)C++17
100 / 100
443 ms30736 KiB
/** * author : pham van sam * created : 27 June 2023 (Tuesday) **/ #include <bits/stdc++.h> using namespace std; using namespace chrono; #define MASK(x) (1LL << (x)) #define BIT(x, i) (((x) >> (i)) & 1) #define ALL(x) (x).begin(), (x).end() #define REP(i, n) for (int i = 0, _n = n; i < _n; ++i) #define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i) #define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i) #define FORE(it, s) for (__typeof(s.begin()) it = (s).begin(); it != (s).end(); ++it) template <typename U, typename V> bool maximize(U &A, const V &B) { return (A < B) ? (A = B, true) : false; } template <typename U, typename V> bool minimize(U &A, const V &B) { return (A > B) ? (A = B, true) : false; } const int MAXN = 1e6 + 5; const int LOG = 30; int N, a[MAXN]; int sum_xor(vector <int> a) { int n = (int) a.size(); int ans = 0; REP(bit, LOG) { vector <int> bit0, bit1, b(n); REP(i, n) (BIT(a[i], bit) ? bit1 : bit0).push_back(a[i]); copy(ALL(bit0), a.begin()); copy(ALL(bit1), a.begin() + (int) bit0.size()); int j = n, k = n, l = n; REP(i, n) b[i] = a[i] & (MASK(bit + 1) - 1); REP(i, n) { if(j < i) j = i; if(k < i) k = i; if(l < i) l = i; while(j > i && b[j - 1] + b[i] >= MASK(bit)) --j; while(k > i && b[k - 1] + b[i] >= MASK(bit + 1)) --k; while(l > i && b[l - 1] + b[i] >= MASK(bit) + MASK(bit + 1)) --l; if((k - j + n - l) & 1) ans ^= MASK(bit); } } return ans; } void process(void) { cin >> N; REP(i, N) cin >> a[i]; cout << sum_xor(vector <int> (a, a + N)); } signed main() { #define TASK "TASK" if(fopen(TASK".inp", "r")) { freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout); } ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); auto start_time = steady_clock::now(); int test = 1; // cin >> test; for (int i = 1; i <= test; ++i) { process(); // cout << '\n'; } auto end_time = steady_clock::now(); cerr << "\nExecution time : " << duration_cast<milliseconds> (end_time - start_time).count() << "[ms]" << endl; return (0 ^ 0); }

Compilation message (stderr)

xorsum.cpp: In function 'int main()':
xorsum.cpp:60:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
xorsum.cpp:61:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         freopen(TASK".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#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...