| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 874604 |
2023-11-17T11:24:50 Z |
sleepntsheep |
XOR (IZhO12_xor) |
C++17 |
|
153 ms |
47336 KB |
#include <assert.h>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#define int long long
#define N 250000
#define M 9000000
int n, x, z, zz;
int a[N+1];
int A[M], C[M][2], alloc = 1;
int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }
void insert(int v, int x, int j, int i)
{
int b = (x >> j) & 1;
A[v] = max(A[v], i);
if (j >= 0)
{
if (!C[v][b]) C[v][b] = ++alloc;
insert(C[v][b], x, j-1, i);
A[v] = max(A[v], A[C[v][b]]);
}
}
int query(int v, int x, long long y, int j)
{
if (y <= 0) return A[v];
int b = (x >> j) & 1, z = -1;
if (j >= 0)
{
if ((1u << j) >= y)
{
z = max(A[C[v][b^1]], query(C[v][b], x, y, j-1));
}
else
{
z = query(C[v][b^1], x, y - (1ll << j), j-1);
}
}
return z;
}
signed main(void)
{
scanf("%lld%lld", &n, &x);
for (int i = 1; i <= n; ++i) scanf("%lld", a+i), insert(1, a[i] ^= a[i-1], 30, i);
for (int b, i = 0; i < n; ++i) if ((b = query(1, a[i], x, 30) - i) > z) z = b, zz = i + 1;
assert(z);
printf("%lld %lld", zz, z);
return 0;
}
#if 0
#include <assert.h>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#define int long long
#define N 250000
#define M 9000000
int n, x, z = -1, zz;
int a[N+2];
int A[M], C[M][2], alloc = 1;
int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }
void insert(int v, int x, int j, int i)
{
int b = (x >> j) & 1;
A[v] = max(A[v], i);
if (j >= 0)
{
if (!C[v][b]) C[v][b] = ++alloc;
insert(C[v][b], x, j-1, i);
A[v] = max(A[v], A[C[v][b]]);
}
}
int query(int v, int x, long long y, int j)
{
if (!v) return -1;
if (y <= 0) return A[v];
int b = (x >> j) & 1, z = -1;
if (j >= 0)
{
if ((1u << j) >= y)
{
z = max(A[C[v][b^1]], query(C[v][b], x, y, j-1));
}
else
{
z = query(C[v][b^1], x, y - (1ll << j), j-1);
}
}
return z;
}
signed main(void)
{
scanf("%lld%lld", &n, &x);
insert(1, 0, 31, n+1);
for (int i = n; i >= 1; --i)
{
scanf("%lld", a+i);
a[i] ^= a[i+1];
int b = query(1, a[i], x, 31) - i;
if (b >= z) z = b, zz = i;
insert(1, a[i], 31, i);
}
assert(z != -1);
printf("%lld %lld", zz, z);
return 0;
}
#endif
Compilation message
xor.cpp: In function 'int main()':
xor.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
50 | scanf("%lld%lld", &n, &x);
| ~~~~~^~~~~~~~~~~~~~~~~~~~
xor.cpp:51:39: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
51 | for (int i = 1; i <= n; ++i) scanf("%lld", a+i), insert(1, a[i] ^= a[i-1], 30, i);
| ~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 5 |
Correct |
8 ms |
3460 KB |
Output is correct |
| 6 |
Correct |
11 ms |
3772 KB |
Output is correct |
| 7 |
Correct |
11 ms |
3624 KB |
Output is correct |
| 8 |
Correct |
13 ms |
3676 KB |
Output is correct |
| 9 |
Correct |
56 ms |
23052 KB |
Output is correct |
| 10 |
Correct |
51 ms |
23092 KB |
Output is correct |
| 11 |
Correct |
51 ms |
22984 KB |
Output is correct |
| 12 |
Correct |
51 ms |
22868 KB |
Output is correct |
| 13 |
Correct |
61 ms |
23140 KB |
Output is correct |
| 14 |
Correct |
54 ms |
22996 KB |
Output is correct |
| 15 |
Correct |
53 ms |
23124 KB |
Output is correct |
| 16 |
Correct |
59 ms |
22864 KB |
Output is correct |
| 17 |
Correct |
149 ms |
47300 KB |
Output is correct |
| 18 |
Correct |
152 ms |
47264 KB |
Output is correct |
| 19 |
Correct |
153 ms |
47336 KB |
Output is correct |
| 20 |
Correct |
150 ms |
47172 KB |
Output is correct |
