oj.uz

Submission #320777

# Submission time Handle Problem Language Result Execution time Memory
320777 2020-11-09T21:46:44 Z SavicS XOR (IZhO12_xor) C++14
100 / 100
 152 ms 35684 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define all(a) a.begin(), a.end()
#define ff(i,a,b) for(int i=a;i<=b;i++)
#define fb(i,b,a) for(int i=b;i>=a;i--)

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 5000005;
const int inf = 1e9 + 5;

int n, a;

int najm[maxn];

int idx;
int lipa[maxn][2];
bool kraj[maxn];
void add(int x, int id){
    int tr = 0;
    fb(mask,29,0){
        int c = 0;
        if((1 << mask) & x)c = 1;
        if(!lipa[tr][c])lipa[tr][c] = ++idx;
        tr = lipa[tr][c];
        najm[tr] = min(najm[tr], id);
//         cout << "tr: " << tr << endl;
    }
    kraj[tr] = 1;
}
int kve(int x){
    int tr = 0;
    int ans = inf;
    fb(mask,29,0){
        // 1
//        cout << "tr: " << tr << endl;
        if((1 << mask) & a){
            if((1 << mask) & x){
                // 11
//                cout << 11 << endl;
                if(!lipa[tr][0])break;
                tr = lipa[tr][0];
            }
            else{
                // 10
//                cout << 10 << endl;
                if(!lipa[tr][1])break;
                tr = lipa[tr][1];
            }
        }
        // 0
        else{
            if((1 << mask) & x){
                // 01
//                cout << "01" << endl;
                if(lipa[tr][0])ans = min(ans, najm[lipa[tr][0]]);
                if(!lipa[tr][1])break;
                tr = lipa[tr][1];
            }
            else{
                //00
//                cout << "00" << endl;
                if(lipa[tr][1])ans = min(ans, najm[lipa[tr][1]]);
                if(!lipa[tr][0])break;
                tr = lipa[tr][0];
            }
        }
//        cout << endl;
    }
//    cout << "tr: " << tr << endl;
    if(kraj[tr])ans = min(ans, najm[tr]);
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cout.tie(nullptr);
    cin.tie(nullptr);
    cin >> n >> a;
    ff(i,0,maxn - 1)najm[i] = inf;
    add(0, 0);
    int pref = 0;
    int len = 0;
    int poz = 0;
    ff(i,1,n){
        int x;
        cin >> x;
        pref ^= x;
        int levo = kve(pref) + 1;
//        cout << "levo: " << levo << endl;
        if(i - levo + 1 > len){
            len = i - levo + 1;
            poz = levo;
        }
        add(pref, i);
    }
    cout << poz << " " << len << endl;
    return 0;
}
/**
4 6
6 1 2 4


1 6
6

4 0
5 5 5 5
**/

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19948 KB Output is correct
2 Correct 12 ms 19948 KB Output is correct
3 Correct 12 ms 19948 KB Output is correct
4 Correct 12 ms 19948 KB Output is correct
5 Correct 18 ms 20332 KB Output is correct
6 Correct 20 ms 20332 KB Output is correct
7 Correct 20 ms 20332 KB Output is correct
8 Correct 21 ms 20332 KB Output is correct
9 Correct 54 ms 27364 KB Output is correct
10 Correct 57 ms 27364 KB Output is correct
11 Correct 74 ms 27364 KB Output is correct
12 Correct 57 ms 27492 KB Output is correct
13 Correct 57 ms 27364 KB Output is correct
14 Correct 54 ms 27492 KB Output is correct
15 Correct 57 ms 27364 KB Output is correct
16 Correct 57 ms 27364 KB Output is correct
17 Correct 150 ms 35684 KB Output is correct
18 Correct 141 ms 35684 KB Output is correct
19 Correct 151 ms 35684 KB Output is correct
20 Correct 152 ms 35684 KB Output is correct