| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 681360 |
2023-01-12T21:01:32 Z |
USER |
XOR Sum (info1cup17_xorsum) |
C++14 |
|
1600 ms |
29844 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');
}
}
};
Input fin;
Output fout;
ofstream out("number.out");
// (((1 << k) <= nr && nr < (1 << (k + 1))) || (nr >= (1 << k) + (1 << (k + 1))))
int v[1000001], X[1000001], n, POW[32], szX, szY, low[1000001], high[1000001];
int* vp, * xp;
bool bit;
struct poz {
int val, i;
}a[1000002], x[1000001], y[1000001];
bitset <1000001> b;
int main()
{
cin >> n;
int maxi = 0;
for (int i = 0; i <= 30; i++)
POW[i] = (1 << i);
for (int i = 1; i <= n; i++)
{
cin >> v[i];
maxi = max(maxi, v[i]);
}
//cout << '\n';
int stop = ceil(log2(maxi)) + 1;
int l, r, m, poz1, poz2, poz;
int res = 0, downLim, upLim, aux, sz, i;
for (int i = 1; i <= n; i++)
a[i].i = i, a[i].val = 0;
for (int k = 0; k <= stop; k++)
{
bit = false;
vp = v;
vp++;
xp = X;
xp++;
szX = szY = 0;
for (i = 1; i <= n; i++)
{
if (*vp & 1)
*xp += POW[k], b[i] = true;
else
b[i] = false;
*vp >>= 1;
vp++;
xp++;
}
for (i = 1; i <= n; i++)
if (b[a[i].i])
a[i].val += POW[k], y[++szY] = a[i];
else
x[++szX] = a[i];
for (i = 1; i <= szX; i++)
a[i] = x[i];
for (int i = 1; i <= szY; i++)
a[szX + i] = y[i];
aux = (1 << k) + (1 << (k + 1));
downLim = POW[k];
upLim = POW[k + 1] - 1;
//cout << aux << ' ' << downLim << ' ' << upLim << '\n';
//for (int i = 1; i <= n; i++)
// cout << a[i].val << ' ';
//cout << '\n';
// case 1 --- (nr >= (1 << k) + (1 << (k + 1)))
for (int i = 1; i <= n; i++)
{
poz = -1;
l = i, r = n;
while (l <= r)
{
m = (l + r) >> 1;
if (a[i].val + a[m].val >= aux)
{
poz = m;
r = m - 1;
}
else
l = m + 1;
}
if (poz != -1)
bit ^= (n - poz + 1) & 1;
}
//l = 1, r = 1;
//while (r <= n && a[l].val + a[r].val < aux)
// r++;
//if (r == n + 1)
//{
// while (l <= n && a[l].val + a[n].val < aux)
// l++; /*cout << 0 << ' ';*/
// r = n;
//}
//if (l != n + 1 && r != n + 1)
//{
// while (l < r)
// {
// while (l < r && a[l].val + a[r - 1].val >= aux)
// r--;
// bit ^= (n - r + 1) & 1;
// //cout << r << ' ';
// l++;
// }
// while (l <= n)
// bit ^= (n - (l++) + 1) & 1; /*cout << l - 1 << ' ';*/
//}
//cout << '\n';
// case 2 --- (1 << k) <= nr && nr < (1 << (k + 1))
// calc. down limit for each "i"
/*l = 1, r = 1;
while (r <= n && a[1].val + a[r].val < downLim)
r++;
if (r == n + 1)
{
while (l <= n && a[l].val + a[n].val < downLim)
low[l++] = 0;
r = n;
}
if (l != n + 1 && r != n + 1)
{
while (l < r)
{
while (l < r && a[l].val + a[r - 1].val >= downLim)
r--;
low[l] = r;
l++;
}
while (l <= n)
low[l] = l++;
}*/
for (int i = 1; i <= n; i++)
{
poz1 = -1;
l = i, r = n;
while (l <= r)
{
m = (l + r) >> 1;
if (a[i].val + a[m].val >= downLim)
{
poz1 = m;
r = m - 1;
}
else
l = m + 1;
}
if (poz1 == -1 || a[i].val + a[poz1].val > upLim)
continue;
l = poz1, r = n;
while (l <= r)
{
m = (l + r) >> 1;
if (a[i].val + a[m].val <= upLim)
{
poz2 = m;
l = m + 1;
}
else
r = m - 1;
}
bit ^= (poz2 - poz1 + 1) & 1;
}
// calc. up limit for each "i"
/*l = 1, r = n;
while (r && a[1].val + a[r].val > upLim)
r--;
if (r)
{
while (true)
{
while (l <= r && a[l].val + a[r].val > upLim)
r--;
if (r < l)
break;
high[l] = r;
l++;
}
while (l <= n)
high[l++] = 0;
}
else
{
for (i = 1; i <= n; i++)
high[i] = 0;
}*/
// use limits
//for (i = 1; i <= n; i++)
// cout << low[i] << ' ';
//cout << '\n';
//for (i = 1; i <= n; i++)
// cout << high[i] << ' ';
//cout << '\n' << '\n';
/*for (i = 1; i <= n; i++)
if (low[i] && high[i] && low[i] <= high[i])
bit ^= (high[i] - low[i] + 1) & 1;*/
if (bit)
res += POW[k];
}
cout << res;
return 0;
}
Compilation message
xorsum.cpp: In function 'int main()':
xorsum.cpp:269:39: warning: unused variable 'sz' [-Wunused-variable]
269 | int res = 0, downLim, upLim, aux, sz, i;
| ^~
xorsum.cpp:444:26: warning: 'poz2' may be used uninitialized in this function [-Wmaybe-uninitialized]
444 | bit ^= (poz2 - poz1 + 1) & 1;
| ~~~~~^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
468 KB |
Output is correct |
| 2 |
Correct |
10 ms |
476 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1288 ms |
29740 KB |
Output is correct |
| 2 |
Correct |
1196 ms |
29844 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1288 ms |
29740 KB |
Output is correct |
| 2 |
Correct |
1196 ms |
29844 KB |
Output is correct |
| 3 |
Execution timed out |
1685 ms |
28548 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
468 KB |
Output is correct |
| 2 |
Correct |
10 ms |
476 KB |
Output is correct |
| 3 |
Correct |
276 ms |
4200 KB |
Output is correct |
| 4 |
Correct |
276 ms |
4208 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
468 KB |
Output is correct |
| 2 |
Correct |
10 ms |
476 KB |
Output is correct |
| 3 |
Correct |
1288 ms |
29740 KB |
Output is correct |
| 4 |
Correct |
1196 ms |
29844 KB |
Output is correct |
| 5 |
Execution timed out |
1685 ms |
28548 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
