# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
680806 | 2023-01-11T20:13:34 Z | iosif_andrei_ | XOR Sum (info1cup17_xorsum) | C++14 | 1600 ms | 27612 KB |
#include <bits/stdc++.h> using namespace std; class input { private: char* t; int sp; const int sz = 10000; char read() { if (sp == sz) { fread(t, 1, sz, stdin); sp = 0; return t[sp++]; } else return t[sp++]; } public: input() { sp = sz; t = new char[sz](); } inline input& operator >> (int& n) { char c = read(); while (c == ' ' || c == '\n') c = read(); n = 0; int sng = 1; if (c == '-') sng = -1, c = read(); while (c != '\0' && isdigit(c)) n = n * 10 + (c - '0'), c = read(); n *= sng; return *this; } input& operator >> (char& s) { char c = read(); while (c != '\0' && c == '\n') c = read(); s = c; return *this; } input& operator >> (long long& n) { char c = read(); while (c == ' ' || c == '\n') c = read(); n = 0; int sng = 1; if (c == '-') sng = -1, c = read(); while (c != '\0' && isdigit(c)) n = n * 10 + (c - '0'), c = read(); n *= sng; return *this; } void getline(string& s) { char c = read(); s = ""; while (c != '\0' && c != '\n') s += c, c = read(); } input& operator >> (string& s) { char c; c = read(); s = ""; while (c == '\n' || c == ' ') c = read(); while (c != '\n' && c != '\0' && c != ' ') s += c, c = read(); return *this; } input& operator >> (char* s) { char c; c = read(); int i = 0; while (c == '\n' || c == ' ') c = read(); while (c != '\n' && c != '\0' && c != ' ') s[i++] = c, c = read(); return *this; } }; class output { private: char* t; int sp; const int sz = 10000; void write(char c) { if (sp == sz) { fwrite(t, 1, sz, stdout); sp = 0; t[sp++] = c; } else t[sp++] = c; } public: output() { sp = 0; t = new char[sz](); } ~output() { fwrite(t, 1, sp, stdout); } output& operator << (int n) { if (n < 0) { write('-'); n *= -1; } if (n <= 9) write(char(n + '0')); else { (*this) << (n / 10); write(char(n % 10 + '0')); } return *this; } output& operator << (char c) { write(c); return *this; } output& operator << (const char* s) { int i = 0; while (s[i] != '\0') write(s[i++]); return *this; } output& operator << (long long n) { if (n < 0) { write('-'); n *= -1; } if (n < 10) write(char(n + '0')); else { (*this) << (n / 10); write(char(n % 10 + '0')); } return *this; } output& operator << (string s) { for (auto i : s) write(i); return *this; } void precizion(double x, int nr) { int p = int(floor(x)); *this << p; if (nr == 0) return; write('.'); for (int i = 1; i <= nr; i++) { x -= floor(x); x *= 10; write(int(x) + '0'); } } }; input fin; output fout; // (((1 << k) <= nr && nr < (1 << (k + 1))) || (nr >= (1 << k) + (1 << (k + 1)))) int v[1000001], x[1000001], n, t[1000002]; int* vp, * xp, * p; long long bit[30]; const int inf = 100000000; inline void add(int poz) { for (int i = poz; i <= n; i += (i & -i)) t[i]++; } inline void remove(int poz) { for (int i = poz; i <= n; i += (i & -i)) t[i]++; } inline int get(int poz) { int s = 0; for (int i = poz; i; i -= (i & -i)) s += t[i]; return s; } inline void reset() { p = (t + 1); while (*p != -1) *p = 0, p++; } struct poz { int val, i; }a[1000001], z2[1000001]; void Sort(int l, int r) { if (l == r) return; int m = (l + r) >> 1; Sort(l, m); Sort(m + 1, r); int i = l, j = m + 1, sz = 0; while (i <= m && j <= r) if (a[i].val < a[j].val) z2[sz++] = a[i++]; else z2[sz++] = a[j++]; while (i <= m) z2[sz++] = a[i++]; while (j <= r) z2[sz++] = a[j++]; for (i = l, j = 0; i <= r; i++, j++) a[i] = z2[j]; } int main() { fin >> n; t[n + 1] = -1; int maxi = 0; for (int i = 1; i <= n; i++) fin >> v[i], maxi = max(maxi, v[i]); int stop = ceil(log2(maxi)); int i, k, l, r, aux; for (k = 0; k <= stop; k++) { // init. pointer for v vp = v; vp++; // init pointer for x xp = x; xp++; for (i = 1; i <= n; i++) { if (*vp & 1) *xp += (1 << k); *vp >>= 1; a[i].val = *xp; a[i].i = i; vp++; xp++; add(1); } Sort(1, n); reset(); } int res = 0; for (int k = 0; k <= 29; k++) if (bit[k] & 1) res += (1 << k); fout << res; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 11 ms | 468 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1686 ms | 27612 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1686 ms | 27612 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 11 ms | 468 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 11 ms | 468 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |