oj.uz

Submission #13333

# Submission time Handle Problem Language Result Execution time Memory
13333 2015-02-11T17:43:36 Z dohyun0324 XOR (IZhO12_xor) C++
85 / 100
 2000 ms 100420 KB 
#include<stdio.h>
#include<map>
#include<string.h>
using namespace std;
map<int,int>ch;
int ans,p,len,n,x,a[250010],b[250010],sum[250010],dap[250010],t,r;
int main()
{
    int i,j;
    scanf("%d %d",&n,&x);
    for(i=1;i<=n;i++) scanf("%d",&a[i]);
    for(i=30;i>=0;i--){
        r=1<<i; t+=r;
        if(x&r){
            for(j=1;j<=n;j++){
                if(r&a[j]) b[j]+=r;
                sum[j]=sum[j-1]^b[j];
            }
        }
        else{
            for(j=1;j<=n;j++){
                if(r&a[j]) b[j]+=r;
                sum[j]=sum[j-1]^b[j];
                ch[sum[j]]=j;
            }
            for(j=1;j<=n;j++) dap[j]=max(dap[j],ch[sum[j-1]^t]);
            for(j=1;j<=n;j++) ch[sum[j]]=0;
            t-=r;
        }
    }
    for(j=1;j<=n;j++) ch[sum[j]]=j;
    for(j=1;j<=n;j++) dap[j]=max(dap[j],ch[sum[j-1]^t]);
    for(i=1;i<=n;i++){
        if(ans<dap[i]-i+1) ans=dap[i]-i+1, p=i;
    }
    printf("%d %d",p,ans);
    return 0;
}

Subtask #1
85.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5120 KB Output is correct
2 Correct 0 ms 5120 KB Output is correct
3 Correct 0 ms 5120 KB Output is correct
4 Correct 3 ms 5384 KB Output is correct
5 Correct 20 ms 6572 KB Output is correct
6 Correct 44 ms 7232 KB Output is correct
7 Correct 27 ms 6968 KB Output is correct
8 Correct 28 ms 6968 KB Output is correct
9 Correct 735 ms 39572 KB Output is correct
10 Correct 774 ms 40364 KB Output is correct
11 Correct 582 ms 35744 KB Output is correct
12 Correct 592 ms 33368 KB Output is correct
13 Correct 423 ms 29408 KB Output is correct
14 Correct 546 ms 33632 KB Output is correct
15 Correct 1094 ms 51056 KB Output is correct
16 Correct 433 ms 28088 KB Output is correct
17 Execution timed out 2000 ms 97916 KB Program timed out
18 Execution timed out 2000 ms 88148 KB Program timed out
19 Execution timed out 2000 ms 100420 KB Program timed out
20 Correct 1890 ms 76664 KB Output is correct