| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 681229 |
2023-01-12T14:51:49 Z |
USER |
XOR Sum (info1cup17_xorsum) |
C++14 |
|
1600 ms |
72512 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]();
}
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');
}
}
};
struct nod {
int val, hight, nr, fr;
nod* left, * right;
};
nod* root;
nod* x, * y, * z;
int leftH, rightH, b;
inline nod* add(nod* root, int val)
{
if (root == NULL)
{
nod* p = new nod;
p->val = val;
p->left = p->right = NULL;
p->nr = p->hight = 1;
p->fr = 1;
return p;
}
if (root->val < val)
root->right = add(root->right, val);
else if (root->val > val)
root->left = add(root->left, val);
else
{
root->fr++;
root->nr++;
return root;
}
leftH = (root->left == NULL ? 0 : root->left->hight);
rightH = (root->right == NULL ? 0 : root->right->hight);
root->hight = max(leftH, rightH) + 1;
root->nr = (root->left == NULL ? 0 : root->left->nr) + (root->right == NULL ? 0 : root->right->nr) + root->fr;
b = leftH - rightH;
if (b > 1)
{
if (val < root->left->val)
{
x = root;
nod* y = x->left;
nod* z = y->right;
y->right = x;
x->left = z;
if ((x->left == NULL ? 0 : x->left->hight) > (x->right == NULL ? 0 : x->right->hight))
x->hight = (x->left == NULL ? 0 : x->left->hight) + 1;
else
x->hight = (x->right == NULL ? 0 : x->right->hight) + 1;
if ((y->left == NULL ? 0 : y->left->hight) > (y->right == NULL ? 0 : y->right->hight))
y->hight = (y->left == NULL ? 0 : y->left->hight) + 1;
else
y->hight = (y->right == NULL ? 0 : y->right->hight) + 1;
x->nr = (x->left == NULL ? 0 : x->left->nr) + (x->right == NULL ? 0 : x->right->nr) + x->fr;
y->nr = (y->right == NULL ? 0 : y->right->nr) + (y->left == NULL ? 0 : y->left->nr) + y->fr;
return y;
}
else
{
x = root->left;
y = x->right;
z = y->left;
y->left = x;
x->right = z;
if ((x->left == NULL ? 0 : x->left->hight) > (x->right == NULL ? 0 : x->right->hight))
x->hight = (x->left == NULL ? 0 : x->left->hight) + 1;
else
x->hight = (x->right == NULL ? 0 : x->right->hight) + 1;
if ((y->left == NULL ? 0 : y->left->hight) > (y->right == NULL ? 0 : y->right->hight))
y->hight = (y->left == NULL ? 0 : y->left->hight) + 1;
else
y->hight = (y->right == NULL ? 0 : y->right->hight) + 1;
x->nr = (x->left == NULL ? 0 : x->left->nr) + (x->right == NULL ? 0 : x->right->nr) + x->fr;
y->nr = (y->right == NULL ? 0 : y->right->nr) + (y->left == NULL ? 0 : y->left->nr) + y->fr;
root->left = y;
x = root;
y = x->left;
z = y->right;
y->right = x;
x->left = z;
if ((x->left == NULL ? 0 : x->left->hight) > (x->right == NULL ? 0 : x->right->hight))
x->hight = (x->left == NULL ? 0 : x->left->hight) + 1;
else
x->hight = (x->right == NULL ? 0 : x->right->hight) + 1;
if ((y->left == NULL ? 0 : y->left->hight) > (y->right == NULL ? 0 : y->right->hight))
y->hight = (y->left == NULL ? 0 : y->left->hight) + 1;
else
y->hight = (y->right == NULL ? 0 : y->right->hight) + 1;
x->nr = (x->left == NULL ? 0 : x->left->nr) + (x->right == NULL ? 0 : x->right->nr) + x->fr;
y->nr = (y->right == NULL ? 0 : y->right->nr) + (y->left == NULL ? 0 : y->left->nr) + y->fr;
return y;
}
}
else if (b < -1)
{
if (val > root->right->val)
{
x = root;
y = x->right;
z = y->left;
y->left = x;
x->right = z;
if ((x->left == NULL ? 0 : x->left->hight) > (x->right == NULL ? 0 : x->right->hight))
x->hight = (x->left == NULL ? 0 : x->left->hight) + 1;
else
x->hight = (x->right == NULL ? 0 : x->right->hight) + 1;
if ((y->left == NULL ? 0 : y->left->hight) > (y->right == NULL ? 0 : y->right->hight))
y->hight = (y->left == NULL ? 0 : y->left->hight) + 1;
else
y->hight = (y->right == NULL ? 0 : y->right->hight) + 1;
x->nr = (x->left == NULL ? 0 : x->left->nr) + (x->right == NULL ? 0 : x->right->nr) + x->fr;
y->nr = (y->right == NULL ? 0 : y->right->nr) + (y->left == NULL ? 0 : y->left->nr) + y->fr;
return y;
}
else
{
x = root->right;
y = x->left;
z = y->right;
y->right = x;
x->left = z;
if ((x->left == NULL ? 0 : x->left->hight) > (x->right == NULL ? 0 : x->right->hight))
x->hight = (x->left == NULL ? 0 : x->left->hight) + 1;
else
x->hight = (x->right == NULL ? 0 : x->right->hight) + 1;
if ((y->left == NULL ? 0 : y->left->hight) > (y->right == NULL ? 0 : y->right->hight))
y->hight = (y->left == NULL ? 0 : y->left->hight) + 1;
else
y->hight = (y->right == NULL ? 0 : y->right->hight) + 1;
x->nr = (x->left == NULL ? 0 : x->left->nr) + (x->right == NULL ? 0 : x->right->nr) + x->fr;
y->nr = (y->right == NULL ? 0 : y->right->nr) + (y->left == NULL ? 0 : y->left->nr) + y->fr;
root->right = y;
x = root;
y = x->right;
z = y->left;
y->left = x;
x->right = z;
if ((x->left == NULL ? 0 : x->left->hight) > (x->right == NULL ? 0 : x->right->hight))
x->hight = (x->left == NULL ? 0 : x->left->hight) + 1;
else
x->hight = (x->right == NULL ? 0 : x->right->hight) + 1;
if ((y->left == NULL ? 0 : y->left->hight) > (y->right == NULL ? 0 : y->right->hight))
y->hight = (y->left == NULL ? 0 : y->left->hight) + 1;
else
y->hight = (y->right == NULL ? 0 : y->right->hight) + 1;
x->nr = (x->left == NULL ? 0 : x->left->nr) + (x->right == NULL ? 0 : x->right->nr) + x->fr;
y->nr = (y->right == NULL ? 0 : y->right->nr) + (y->left == NULL ? 0 : y->left->nr) + y->fr;
return y;
}
}
return root;
}
input fin;
output fout;
// (((1 << k) <= nr && nr < (1 << (k + 1))) || (nr >= (1 << k) + (1 << (k + 1))))
int v[1000001], X[1000001], n, POW[32];
int* vp, * xp;
nod* p;
bool bit;
int main()
{
int maxi = 0;
for (int i = 0; i <= 30; i++)
POW[i] = (1 << i);
fin >> n;
for (int i = 1; i <= n; i++)
fin >> v[i], maxi = max(maxi, v[i]);
int stop = ceil(log2(maxi)) + 1, aux, l, r;
nod* rod;
int res = 0;
for (int k = 0; k <= stop; k++)
{
bit = false;
vp = v;
vp++;
xp = X;
xp++;
for (int i = 1; i <= n; i++)
{
if (*vp & 1)
*xp += POW[k];
*vp >>= 1;
if (root == NULL)
{
root = new nod;
root->nr = root->hight = 1;
root->left = root->right = NULL;
root->val = *xp;
root->fr = 1;
}
else
root = add(root, *xp);
//bit[k] += S.interval(POW[k] - *xp, POW[k + 1] - *xp - 1); + S.greaterThan(POW[k] + POW[k + 1] - *xp);
aux = POW[k] + POW[k + 1] - *xp;
p = root;
while (p)
{
if (p->val < aux)
p = p->right;
else
{
bit = (bit ^ (((p->right == NULL ? 0 : p->right->nr) + p->fr) & 1));
p = p->left;
}
}
l = POW[k] - *xp;
r = POW[k + 1] - *xp - 1;
p = root;
while (p)
{
if (p->val < l)
p = p->right;
else if (p->val > r)
p = p->left;
else
break;
}
if (p)
{
bit = bit ^ (p->fr & 1);
rod = p->left;
while (rod)
{
if (rod->val < l)
rod = rod->right;
else
{
bit = bit ^ (((rod->right == NULL ? 0 : rod->right->nr) + rod->fr) & 1);
rod = rod->left;
}
}
rod = p->right;
while (rod)
{
if (rod->val > r)
rod = rod->left;
else
{
bit = bit ^ (((rod->left == NULL ? 0 : rod->left->nr) + rod->fr) & 1);
rod = rod->right;
}
}
}
vp++;
xp++;
}
if (bit)
res += POW[k];
root = NULL;
}
fout << res;
return 0;
}
Compilation message
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 |
28 ms |
3988 KB |
Output is correct |
| 2 |
Correct |
30 ms |
4008 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1570 ms |
8824 KB |
Output is correct |
| 2 |
Correct |
1465 ms |
8300 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1570 ms |
8824 KB |
Output is correct |
| 2 |
Correct |
1465 ms |
8300 KB |
Output is correct |
| 3 |
Execution timed out |
1687 ms |
9656 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
3988 KB |
Output is correct |
| 2 |
Correct |
30 ms |
4008 KB |
Output is correct |
| 3 |
Correct |
1184 ms |
72512 KB |
Output is correct |
| 4 |
Correct |
1175 ms |
72476 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
3988 KB |
Output is correct |
| 2 |
Correct |
30 ms |
4008 KB |
Output is correct |
| 3 |
Correct |
1570 ms |
8824 KB |
Output is correct |
| 4 |
Correct |
1465 ms |
8300 KB |
Output is correct |
| 5 |
Execution timed out |
1687 ms |
9656 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
