제출 #1268253

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1268253		iamarman	XOR (IZhO12_xor)	C++20	0 / 100	2020 ms	34204 KiB

xor

                                                  //   Bismillahir Rahmanir Rahim      //
                                                 //     After hardship comes ease     //
                                                //         AUTHOR : iamarman         //

// pragmas
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
// #pragma GCC optimization ("unroll-loops")
// #pragma GCC optimization ("strict-overflow")
 
#include<bits/stdc++.h>

using namespace std;

                                                    ////       TEMPLATE       ////

//---------------------------------------------------------------------------------------------------------------------------------|


# define    el '\n'
# define    sp " "
# define    ff first
# define    ss second
# define    ll long long
# define    pb push_back
# define    mp make_pair
# define    yess1 cout<<1<<el 
# define    noo cout<<"NO"<<el
# define    yess cout<<"YES"<<el
# define    siz(x) (int)x.size()
# define    ull unsigned long long    
# define    all(v) v.begin(),v.end()
# define    allr(v) v.rbegin(),v.rend()


# define optimise   { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); }

// find_by_order() - Returns an iterator to the k-th largest element (counting from zero)
// order_of_key()  - The number of items in a set that are strictly smaller than our item 
// greater instead of less for descending order
// less_equal works as ordered multiset
// we can use pair<int,int> instead of int for pair of orderd set
// for multiset st.lower_bound(x) works as upper bound and st.upper_bound(x) works as lower bound

inline void file() {
#ifndef ONLINE_JUDGE  
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif // ONLINE_JUDGE
}

 
int dx[]={-1, 1 , 0 , 0 , -1 ,-1, 1, 1};
int dy[]={ 0, 0 ,-1 , 1 , -1 , 1,-1, 1};

// up = { -1,0 } , down = { 1,0 } , right = { 0,1 } , left = { 0,-1 }
// up-right = { -1,1 } , up-left = { -1,-1 } , down-right = { 1,1 } , down-left = { 1,-1 }




                                                   ///  ____________CODE STARTS FROM HERE____________    ///



struct Node {
    int child[2];
    int cnt;
    int anyIndex; // stores an example index of a number passing through this node
    Node(){ child[0]=child[1]=-1; cnt=0; anyIndex=-1; }
};

struct Trie {
    vector<Node> t;
    int B;
    Trie(int bits=31){ B = bits; t.emplace_back(); } // use 31..0 bits by default

    void clear(){ t.clear(); t.emplace_back(); }

    void insert(int val, int idx){
        int cur = 0;
        for(int i = B; i >= 0; --i){
            int b = (val >> i) & 1;
            if(t[cur].child[b] == -1){
                t[cur].child[b] = t.size();
                t.emplace_back();
            }
            cur = t[cur].child[b];
            t[cur].cnt++;
            t[cur].anyIndex = idx; // remember an index that goes through here
        }
    }

    // returns pair<maxxor, index_of_prefix_used_in_trie>
    pair<int,int> query_with_index(int x){
        int cur = 0;
        if(cur == -1) return {0, -1};
        int ans = 0;
        for(int i = B; i >= 0; --i){
            if(cur == -1) break;
            int b = (x >> i) & 1;
            int want = !b;
            if(t[cur].child[want] != -1 && t[t[cur].child[want]].cnt > 0){
                ans |= (1<<i);
                cur = t[cur].child[want];
            } else if(t[cur].child[b] != -1 && t[t[cur].child[b]].cnt > 0){
                cur = t[cur].child[b];
            } else {
                // no path
                cur = -1;
                break;
            }
        }
        int idx = (cur == -1 ? -1 : t[cur].anyIndex);
        return {ans, idx};
    }
};


void solve()
{
    int n, X;
    if(!(cin >> n >> X)) return;
    vector<int> vec(n+1,0);
    for(int i=1;i<=n;i++){
        cin >> vec[i];
        vec[i] ^= vec[i-1];
    }

    Trie trie(29); // 0..29 bits is enough for <=1e9, change to 31 if you prefer
    int bestLen = 0;
    int bestL = -1, bestLenActual = -1;

    auto ok = [&](int len)->bool{
        trie.clear();
        trie.insert(0, 0); // prefix a[0] at index 0
        for(int i = len; i <= n; ++i){
            trie.insert(vec[i-len], i-len);
            auto pr = trie.query_with_index(vec[i]);
            if(pr.first >= X){
                // pr.second is the prefix index j used; subarray is j+1 .. i
                bestL = pr.second + 1;
                bestLenActual = i - pr.second;
                return true;
            }
        }
        return false;
    };

    int lo = 1, hi = n+1;
    while(hi - lo > 1){
        int mid = lo + (hi - lo) / 2;
        if(ok(mid)) lo = mid;
        else hi = mid;
    }

    // re-run to get concrete indices for the maximal length lo
    if(ok(lo)){
        // print start and actual length (>= lo)
        cout << bestL << " " << bestLenActual << "\n";
    } else {
        // no subarray found at all
        cout << -1 << "\n";
    }

}
int main()
{ 
    optimise;
    //file();
    clock_t start= clock();
    int t=1;
   // cin>>t;
    for(int i=1;i<=t;i++)
    {
         //cout<<"Case "<<i<<": ";
        solve();
    }
   // cerr << "Run Time : " <<((double)(clock() - start) / CLOCKS_PER_SEC)<<el;
}

• Subtask 1: 0 / 100