제출 #1282337

#제출 시각아이디문제언어결과실행 시간메모리
1282337yousef_ahemd_maherXOR (IZhO12_xor)C++20
0 / 100
5 ms2240 KiB
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// #define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
using namespace std;
#define ll long long
#define int long long
#define sp " "
#define endl "\n"
#define vi vector<int>
#define all(a) a.begin(), a.end()
#define ON(n, k) ((n | (1LL << k)))
#define OFF(n, k) (((n) & ~(1LL << (k))))
#define isON(n, k) (((n) >> (k)) & 1LL)
#define JOE ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define files freopen("input.txt","r",stdin), freopen("output.txt","w",stdout);
int M = 31;

struct Node {
    int nxt[2];
    int first;
    Node(){nxt[0] = -1,nxt[1] = -1;}
};
struct Tri {
    vector<Node> v = {Node()};
    void add(int num,int idx) {
        int u = 0;
        for (int i = M;i>=0;i--) {
            int state = isON(num,i);
            if (v[u].nxt[state] == -1) {
                v[u].nxt[state] = new_node();
                v[v[u].nxt[state]].first = idx;
            }
            u = v[u].nxt[state];
        }
    }
    int query(int R,int k) {
        int u = 0;
        int first_index = 1e18;
        int i = M;
        for (;i>=0;i--) {
            int Rstate = isON(R,i),Kstate = isON(k,i);
            if (!Kstate) {
                if (!Rstate) {
                    if (v[u].nxt[1] != -1) {
                        first_index = min(first_index,v[v[u].nxt[1]].first);
                    }
                    if (v[u].nxt[0] == -1)
                        break;
                    u = v[u].nxt[0];
                }
                else {
                    if (v[u].nxt[0] != -1) {
                        first_index = min(first_index,v[v[u].nxt[0]].first);
                    }
                    if (v[u].nxt[1] == -1)
                        break;
                    u = v[u].nxt[1];
                }
            }else {
                if (!Rstate) {
                    if (v[u].nxt[1] == -1)
                        break;
                    u = v[u].nxt[1];
                }
                else {
                    if (v[u].nxt[0] == -1)
                        break;
                    u = v[u].nxt[0];
                }
            }
        }

        if (i == -1) { // reached to the end.
            first_index = min(first_index,v[u].first);
        }

        return first_index;
    }
    int new_node() {
        v.emplace_back();
        return v.size() - 1;
    }
};
void solve() {
    int n,x;
    cin>>n>>x;
    vi v(n+1);

    for (int i = 1;i<=n;i++) {
        cin>>v[i];
        v[i] = (v[i] ^ v[i-1]);
    }

    int l = 0,r = -1;
    Tri tri;

    tri.add(v[1],1);
    for (int i = 2;i<=n;i++) {
        int curL = tri.query(v[i],x);
        if (curL!=1e18) {
            if (r - l < i - curL) {
                r = i,l = curL+1;
            }
        }
        tri.add(v[i],i);
    }

    cout << l << sp << r - l + 1 << endl;
}


int32_t main() {
    // C OUT << "Hello world";
    JOE
// #ifndef ONLINE_JUDGE
//     files
// #endif
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...