oj.uz

답안 #13345

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
13345 2015-02-12T13:58:48 Z dohyun0324 XOR (IZhO12_xor) C++14
100 / 100
 1774 ms 123220 KB 
#include<stdio.h>
#include<unordered_map>
#include<string.h>
using namespace std;
unordered_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
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 5492 KB Output is correct
2 Correct 0 ms 5492 KB Output is correct
3 Correct 0 ms 5492 KB Output is correct
4 Correct 2 ms 5756 KB Output is correct
5 Correct 16 ms 7160 KB Output is correct
6 Correct 25 ms 7316 KB Output is correct
7 Correct 15 ms 7184 KB Output is correct
8 Correct 21 ms 7184 KB Output is correct
9 Correct 426 ms 36600 KB Output is correct
10 Correct 454 ms 37260 KB Output is correct
11 Correct 367 ms 34092 KB Output is correct
12 Correct 393 ms 34064 KB Output is correct
13 Correct 261 ms 25680 KB Output is correct
14 Correct 351 ms 34064 KB Output is correct
15 Correct 593 ms 44388 KB Output is correct
16 Correct 251 ms 24888 KB Output is correct
17 Correct 1420 ms 84176 KB Output is correct
18 Correct 1178 ms 77576 KB Output is correct
19 Correct 1774 ms 123220 KB Output is correct
20 Correct 998 ms 69920 KB Output is correct