oj.uz

답안 #321610

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
321610 2020-11-12T21:29:13 Z iliccmarko XOR (IZhO12_xor) C++14
100 / 100
 197 ms 140268 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
#define INF 1000000000
#define LINF 1000000000000000LL
#define pb push_back
#define all(x) x.begin(), x.end()
#define len(s) (int)s.size()
#define test_case { int t; cin>>t; while(t--)solve(); }
#define input(n, v) {for(int i = 0;i<n;i++) cin>>v[i];}
#define output(n, v) {for(int i = 0;i<n;i++) cout<<v[i]<<" "; cout<<endl;}
#define single_case solve();
#define line cout<<"------------"<<endl;
#define ios { ios_base::sync_with_stdio(false); cin.tie(NULL); }
using namespace std;
const int N = 250005;
int n;
pair<int, int> trie[N*35][2];
int ind;
int prefix[N];
int x;

void _insert(int xx, int u)
{
    int node = 0;
    for(int i = 29;i>=0;i--)
    {
        int bit = (xx>>i)&1;
        if(trie[node][bit].second==-1) trie[node][bit] = make_pair(u, ++ind);
        else
            trie[node][bit].first = min(trie[node][bit].first, u);
        node = trie[node][bit].second;
    }
}

int resi(int u)
{
    int xx = prefix[u];
    int m = u;
    int node = 0;
    for(int i = 29;i>=0;i--)
    {
        int bit = ((x>>i)&1)^((xx>>i)&1);
        if(!((x>>i)&1))
        {
            if(trie[node][1^(((xx>>i)&1))].second!=-1)
            {
                m = min(m, trie[node][1^(((xx>>i)&1))].first);
            }
        }
        if(trie[node][bit].second==-1) {/*cout<<u<<"    "<<i<<" "<<endl;*/ return m;}
        if(i==0)
            m = min(trie[node][bit].first, m);
        node = trie[node][bit].second;
    }
    return m;
}

int main()
{
    ios
    cin>>n>>x;
    for(int i = 0;i<N*35;i++)
        trie[i][0].second = trie[i][1].second = -1;
    int last = 0;
    for(int i = 0;i<n;i++)
    {
        int xx;
        cin>>xx;
        prefix[i] = last ^ xx;
        last = prefix[i];
        _insert(prefix[i], i);
    }

    int ans = 0;
    int index;
    for(int i = 0;i<n;i++)
    {
        int k = resi(i) + 1;
        if(i - k + 1 > ans)
        {
            ans = i - k + 1;
            index = k;
        }
    }

    cout<<index+1<<" "<<ans;








    return 0;
}

Compilation message

xor.cpp: In function 'int main()':
xor.cpp:88:20: warning: 'index' may be used uninitialized in this function [-Wmaybe-uninitialized]
   88 |     cout<<index+1<<" "<<ans;
      |                    ^~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 67 ms 137328 KB Output is correct
2 Correct 69 ms 137324 KB Output is correct
3 Correct 67 ms 137324 KB Output is correct
4 Correct 67 ms 137324 KB Output is correct
5 Correct 73 ms 137580 KB Output is correct
6 Correct 74 ms 137580 KB Output is correct
7 Correct 78 ms 137580 KB Output is correct
8 Correct 77 ms 137708 KB Output is correct
9 Correct 104 ms 138476 KB Output is correct
10 Correct 117 ms 138476 KB Output is correct
11 Correct 107 ms 138476 KB Output is correct
12 Correct 104 ms 138476 KB Output is correct
13 Correct 104 ms 138476 KB Output is correct
14 Correct 105 ms 138476 KB Output is correct
15 Correct 109 ms 138476 KB Output is correct
16 Correct 106 ms 138476 KB Output is correct
17 Correct 197 ms 140268 KB Output is correct
18 Correct 195 ms 140268 KB Output is correct
19 Correct 194 ms 140268 KB Output is correct
20 Correct 196 ms 140248 KB Output is correct