Submission #134197


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 || (Y == M && C->V + 1 < L)) 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 1197 Byte
Status WA
Exec Time 163 ms
Memory 14960 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 × 30
WA × 1
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 37 ms 816 KB
10 AC 24 ms 1124 KB
11 AC 25 ms 1060 KB
12 AC 24 ms 992 KB
13 AC 30 ms 2412 KB
14 AC 31 ms 2540 KB
15 AC 33 ms 2924 KB
16 AC 79 ms 6900 KB
17 AC 60 ms 6824 KB
18 AC 163 ms 14960 KB
19 AC 22 ms 928 KB
2 AC 22 ms 800 KB
20 AC 22 ms 928 KB
21 AC 22 ms 800 KB
22 AC 23 ms 864 KB
23 AC 22 ms 880 KB
24 AC 22 ms 924 KB
25 AC 25 ms 1132 KB
26 AC 23 ms 1056 KB
27 AC 27 ms 1444 KB
28 AC 95 ms 9456 KB
29 AC 106 ms 10224 KB
3 AC 22 ms 804 KB
30 AC 69 ms 7152 KB
31 AC 133 ms 10740 KB
4 WA 23 ms 928 KB
5 AC 22 ms 932 KB
6 AC 23 ms 860 KB
7 AC 22 ms 928 KB
8 AC 23 ms 876 KB
9 AC 22 ms 1056 KB