#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;
poz()
{
val = i = 1000000000;
}
}a[1000001], z2[1000001];
struct query {
int x, i;
}q[1000001], z1[1000001];
void sortQuery(int l, int r, int k)
{
if (l >= r)
return;
int m = (l + r) >> 1;
swap(q[l], q[l + k % (r - l + 1)]);
int i = l, j = r, d = 0;
while (i < j)
{
if (q[i].x < q[j].x)
swap(q[i], q[j]), d = 1 - d;
i += d;
j -= 1 - d;
}
sortQuery(l, i - 1, k);
sortQuery(i + 1, r, k);
}
void sortPoz(int l, int r, int k)
{
if (l >= r)
return;
int m = (l + r) >> 1;
swap(a[l], a[l + k % (r - l + 1)]);
int i = l, j = r, d = 0;
while (i < j)
{
if (a[i].val > a[j].val)
swap(a[i], a[j]), d = 1 - d;
i += d;
j -= 1 - d;
}
sortPoz(l, i - 1, k);
sortPoz(i + 1, r, k);
}
int main()
{
fin >> n;
t[n + 1] = -1;
for (int i = 1; i <= n; i++)
fin >> v[i];
int i, k, l, r, aux;
for (k = 0; k <= 29; 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;
q[i] = { *xp, i };
a[i].val = *xp;
a[i].i = i;
vp++;
xp++;
}
sortQuery(1, n, rand());
sortPoz(1, n, rand());
int j = 1;
aux = (1 << (k + 1)) - 1;
while (j <= n && a[1].val > aux - q[j].x)
j++;
l = r = 1;
add(a[1].i);
for (;j <= n; j++)
{
aux = (1 << k) - q[j].x;
while (l < n && a[l].val < aux)
{
remove(a[l].i);
l++;
}
if (a[l].val < aux)
break;
aux = (1 << (k + 1)) - q[j].x - 1;
while (r < n && a[r + 1].val <= aux)
{
r++;
add(a[r].i);
}
bit[k] += get(q[j].i);
}
reset(); // reset AIB
aux = (1 << k) + (1 << (k + 1)) - q[1].x;
l = n + 1;
while (l > 1 && a[l - 1].val >= aux)
{
l--;
add(a[l].i);
}
if (l == n + 1)
continue;
bit[k] += get(q[1].i);
for (j = 2; j <= n; j++)
{
aux = (1 << k) + (1 << (k + 1)) - q[j].x;
while (l <= n && a[l].val < aux)
{
remove(a[l].i);
l++;
}
if (l == n + 1)
break;
bit[k] += get(q[j].i);
}
reset();
}
int res = 0;
for (int k = 0; k <= 29; k++)
if (bit[k] & 1)
res += (1 << k);
fout << res;
return 0;
}
Compilation message
xorsum.cpp: In function 'void sortQuery(int, int, int)':
xorsum.cpp:294:9: warning: unused variable 'm' [-Wunused-variable]
294 | int m = (l + r) >> 1;
| ^
xorsum.cpp: In function 'void sortPoz(int, int, int)':
xorsum.cpp:317:9: warning: unused variable 'm' [-Wunused-variable]
317 | int m = (l + r) >> 1;
| ^
xorsum.cpp: In member function 'char input::read()':
xorsum.cpp:14:18: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
14 | fread(t, 1, sz, stdin);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
58 ms |
16128 KB |
Output is correct |
| 2 |
Correct |
56 ms |
16124 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1695 ms |
31624 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1695 ms |
31624 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
58 ms |
16128 KB |
Output is correct |
| 2 |
Correct |
56 ms |
16124 KB |
Output is correct |
| 3 |
Execution timed out |
1648 ms |
17804 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
58 ms |
16128 KB |
Output is correct |
| 2 |
Correct |
56 ms |
16124 KB |
Output is correct |
| 3 |
Execution timed out |
1695 ms |
31624 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
