Submission #874604

#	Time	Username	Problem	Language	Result	Execution time	Memory
874604		sleepntsheep	XOR (IZhO12_xor)	C++17	100 / 100	153 ms	47336 KiB

xor

#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 (stderr)

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);
      |                                  ~~~~~^~~~~~~~~~~~~

• Subtask 1: 100 / 100