Submission #1141267

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141267		youssefsobhy	XOR (IZhO12_xor)	C++20	100 / 100	226 ms	86812 KiB

xor

/*
    Author YoussefSobhy30
*/


#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
using multi_ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define ll long long int
#define endl "\n"
#define fastread() ios_base::sync_with_stdio(false);cin.tie(NULL);
#define sz(x) (int)x.size()
#define fr(i , begin , end) for (ll i = begin ; i < end ; i++)
#define frr(i , begin , end) for (ll i = begin ; i >= end ; i--)
#define all(ch) ch.begin() , ch.end()
#define allr(ch) ch.rbegin() , ch.rend()
#define ON(n , k) ( (n) | (1 << (k)) )
#define mem(arr) memset(arr , -1 , sizeof arr)
#define kill(x) cout << x << endl ;
#define OFF(n , k) ((n) & ~(1 << (k)))
#define isON(n , k) (((n) >> k) & 1)
#define RV(x) return void (cout << x << endl) ;

const ll inf = 2e18;
const ll MOD = 1e9 + 7;

int dx[] = {1, 0, -1, 0, -1, -1, 1, 1};
int dy[] = {0, -1, 0, 1, -1, 1, -1, 1};
char di[] = {'D', 'L', 'U', 'R'};

ll add(const ll &a, const ll &b) {
    return (a + b + 2 * MOD) % MOD;
}

ll mul(const ll &a, const ll &b) {
    return (a % MOD + MOD) * (b % MOD + MOD) % MOD;
}

ll sub(const ll a, const ll b) {
    return (a % MOD - b % MOD + 2 * MOD) % MOD;
}

ll gcd(ll a, ll b) {
    if (!b) return a;
    return gcd(b, a % b);
}

ll lcm(ll a, ll b) {
    return a * (b / gcd(a, b));
}

const ll N = 5e5 + 10, LOG = 30;

struct Node {
    Node *childs[2];
    ll size[2];
    ll Min_index ;

    Node() {
        childs[0] = childs[1] = nullptr;
        size[0] = size[1] = 0;
        Min_index = inf ;
    }
};

struct BinaryTrie {
    Node *root = new Node();

    void insert(ll x , ll index) {
        Node *cur = root;
        for (ll i = 30; i >= 0; i--) {
            cur->Min_index = min(cur->Min_index , index) ;
            bool idx = x & (1LL << i);
            if (cur->childs[idx] == nullptr) cur->childs[idx] = new Node();
            cur->size[idx]++;
            cur = cur->childs[idx];
        }
        cur->Min_index = min(cur->Min_index , index) ;
    }

    ll Query(ll n , Node *cur , ll ans , ll i , ll x) {
        if (ans >= x) return cur->Min_index;
        if (i == -1) return inf ;
        ll res = inf ;
        if (n & (1LL << i)) {
            if (cur->childs[0] != nullptr)
                res = min(res , Query(n , cur->childs[0] , (ans | (1LL << i)) , i - 1 , x));
            else
                res = min(res , Query(n , cur->childs[1] , ans , i - 1 , x));
        }
        else {
            if (cur->childs[1] != nullptr)
                res = min(res , Query(n , cur->childs[1] , (ans | (1LL << i)) , i - 1 , x));
            else
                res = min(res , Query(n , cur->childs[0] , ans , i - 1 , x));
        }
        return res;
    }
};

void solve() {
    ll n , x ;
    cin >> n >> x;
    vector<ll> a(n);
    for (ll i = 0 ; i < n ; i++) cin >> a[i];
    BinaryTrie trie ;
    trie.insert(0 , 0);
    ll index = 0 , size = 0 , cur = 0 ;
    for (ll i = 0 ; i < n ; i++) {
        cur ^= a[i];
        ll ans = trie.Query(cur , trie.root , 0 , 30 , x);
        trie.insert(cur, i + 1);
        if (i - ans + 1 > size) size = i - ans + 1 , index = ans + 1 ;
        if (i - ans + 1 == size) index = min(ans + 1, index) ;
    }
    cout << index << " " << size << endl ;
} //! CHECK LONG LONG


int main() {
    fastread()
    ll Test = 1;
    // cin >> Test;
    for (int _ = 1; _ <= Test; _++) {
        cout << fixed << showpoint << setprecision(10);
        // cout << "Case #" << _ << ": " ;
        solve();
    }
}

• Subtask 1: 100 / 100