Submission #134196


Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define MP make_pair
#define fs first
#define sd second

const int inf = int(1e9);

struct Node{
    Node* d[2];
    int V;
    Node(){ d[0] = d[1] = 0; V = inf;}
};

int N;
Node * root;

void addNumber(int X, int i){
    Node * C = root;
    C->V = min (C->V, i);
    for (int j = 20; j >= 0; j--){
        int B = ((X >> j) & 1);
        if (C->d[B] == 0)
            C->d[B] = new Node();
        C = C->d[B];
        C->V =min (C->V, i);
    }
}

int main(){
    //freopen("F.inp", "r", stdin);
    scanf("%d", &N);
    int X = 0, L, R, M = 0, A, Y, B;

    root = new Node();
    addNumber(0, 0);

    for (int i = 1; i <= N; i++){
        scanf("%d", &A);
        X ^= A; Y = 0;
        Node * C = root;
        //printf ("i=%d, X=%d\n",i,X);
        for (int j = 20; j >= 0; j--){
            B = !((X >> j) & 1);
            if (C->d[B] == 0) B = !B;
            Y += (B << j) ^ (X & (1 << j));
            C = C->d[B];
        }
        if (Y > M) M = Y, L = C->V + 1, R = i;
        addNumber(X, i);
    }
    printf("%d %d %d\n", M, L, R);
    return 0;
}

Submission Info

Submission Time
Task F - Maximum Segment XOR
User nsinfo
Language C++ (GCC 4.4.7)
Score 0
Code Size 1169 Byte
Status WA
Exec Time 151 ms
Memory 14956 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:33: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
./Main.cpp:40: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result

Judge Result

Set Name All
Score / Max Score 0 / 100
Status
AC × 20
WA × 11
Set Name Test Cases
All 1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 2, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 3, 30, 31, 4, 5, 6, 7, 8, 9
Case Name Status Exec Time Memory
1 AC 66 ms 800 KB
10 AC 38 ms 1064 KB
11 AC 27 ms 992 KB
12 AC 27 ms 1008 KB
13 AC 31 ms 2416 KB
14 WA 32 ms 2552 KB
15 AC 36 ms 2928 KB
16 WA 76 ms 6892 KB
17 WA 60 ms 6884 KB
18 WA 151 ms 14956 KB
19 WA 22 ms 916 KB
2 AC 23 ms 816 KB
20 AC 22 ms 812 KB
21 AC 23 ms 928 KB
22 WA 23 ms 884 KB
23 AC 23 ms 928 KB
24 AC 23 ms 880 KB
25 AC 24 ms 1132 KB
26 WA 25 ms 988 KB
27 WA 28 ms 1400 KB
28 AC 106 ms 9452 KB
29 WA 112 ms 10224 KB
3 AC 23 ms 800 KB
30 AC 69 ms 7148 KB
31 WA 123 ms 10728 KB
4 WA 23 ms 800 KB
5 AC 22 ms 872 KB
6 AC 21 ms 872 KB
7 AC 23 ms 856 KB
8 AC 23 ms 928 KB
9 AC 24 ms 1068 KB