Submission #1146771

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146771		halzoom	XOR (IZhO12_xor)	C++20	0 / 100	0 ms	320 KiB

xor

#include <bits/stdc++.h>
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

using namespace std;
#define ll long long
#define int long long
#define double long double

void UwU() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
}

void fileIO() {
#ifndef ONLINE_JUDGE
    freopen("Input.txt", "r", stdin);
    freopen("Output.txt", "w", stdout);
#endif
}


const ll N = 1e5 + 5;
const ll MOD = 1000000007;
const ll mod = 998244353;
const ll inf = 1e18;
const double EPS = 1e-4;

struct Trie {
private:
    struct Node {
        int child[2]{};
        int cnt = 0, minIDX = inf;

        int &operator[](int x) {
            return child[x];
        }
    };

    vector<Node> node;
public:
    Trie() {
        node.emplace_back();
    }

    int newNode() {
        node.emplace_back();
        return node.size() - 1;
    }

    int sz(int x) {
        return node[x].cnt;
    }

    int M = 30;

    void update(int x, int op, int idx) {
        int cur = 0;
        for (int i = M - 1; i >= 0; --i) {
            int c = x >> i & 1;
            if (node[cur][c] == 0) {
                node[cur][c] = newNode();
            }
            cur = node[cur][c];
            node[cur].cnt += op;
            node[cur].minIDX = min(idx, node[cur].minIDX);
        }
    }

    int query(int t , int x) {
        int cur = 0, res = inf;
        for (int i = M - 1; i >= 0; --i) {
            int ct = (t >> i) & 1;
            int cx = (x >> i) & 1;
            if (sz(node[cur][ct ^ cx]) == 0) {
                break;
            }
            if(cx == 0 and sz(node[cur][!ct])){
                res = min(res , node[node[cur][!ct]].minIDX);
            }
            cur = node[cur][ct ^ cx];
            res = min(res , node[cur].minIDX);
        }
        return res;
    }
};

void solve() {
    int n , X;
    cin >> n >> X;
    Trie trie;
//    trie.update(0 , 1 ,0);
    int prefix = 0;
    int l = 0 , k = 0;
    for(int i = 1 , t ;i <= n ; ++i){
        cin >> t;
        prefix ^= t;
        int x = trie.query(prefix , X);
        if(i - x > k){
            k = i - x;
            l = x + 1;
        }
        trie.update(prefix , 1 , i);
    }

    cout << l << ' ' << k;
}

// BEFORE coding are you sure you understood the statement correctly?
// PLEASE do not forget to read the sample explanation carefully.
// WATCH out for overflows & RTs in general.
// TEST your idea or code on the corner cases.
// ANALYZE each idea you have thoroughly.

signed main() {
    UwU();
    // fileIO();

    int test = 1;
//    cin >> test;

    for (int i = 1; i <= test; ++i) {
        solve();
    }
    return 0;
}

Compilation message (stderr)

xor.cpp: In function 'void fileIO()':
xor.cpp:18:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     freopen("Input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
xor.cpp:19:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     freopen("Output.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100