Submission #1196755

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196755		m_elgamal	XOR (IZhO12_xor)	C++17	100 / 100	181 ms	56640 KiB

xor

#include "bits/stdc++.h"
#define ll long long
#define el '\n'
using namespace std;
const ll N = 2e5 + 3, mod = 1e9 + 7, inf = 1e18;

class BinaryTrie
{
private:
    struct Node
    {
        Node* ch[2];
        int fr, mn;
        Node() : fr(0), mn(mod) {
            memset(ch, 0, sizeof ch);
        }
    };

public:
    Node* root = new Node();
    BinaryTrie() { insert(0, 0); }
    void insert(ll x, int id) {
        Node* cur = root;
        for (int i = 62; i >= 0; i--) {
            int bit = (x >> i) & 1;
            if (!cur->ch[bit])
                cur->ch[bit] = new Node();
            cur = cur->ch[bit];
            cur->fr++;
            cur->mn = min(cur->mn, id);
        }
    }
    void erase(ll x) {
        Node* cur = root;
        for (int i = 62; i >= 0; i--) {
            int bit = (x >> i) & 1;
            cur = cur->ch[bit];
            cur->fr--;
        }
    }
    int query(ll y, ll x) {
        Node* cur = root;
        int id = mod;
        for (int i = 62; i >= 0; i--) {
            int xb = (x >> i) & 1, yb = (y >> i) & 1;

            if (xb == 0 && cur->ch[!yb])
                id = min(id, cur->ch[!yb]->mn + 1);

            xb ^= yb;
            if (!cur->ch[xb])
                return id;
            cur = cur->ch[xb];
        }
        if (cur) 
            id = min(id, cur->mn + 1);
        
        return id;
    }
};
void solve() {
    ll n, x;
    cin >> n >> x;

    BinaryTrie trie;
    ll pre = 0;
    int l = -1, k = -1;

    for (int i = 1; i <= n; i++) {
        ll a;
        cin >> a;
        pre ^= a;

        int j = trie.query(pre, x);
        if (j <= i && (k == -1 || i - j + 1 > k))
            k = i - j + 1, l = j;

        trie.insert(pre, i);
    }
    cout << l << " " << k << el;
}

/*


*/

signed main() {
    ios_base::sync_with_stdio(0);
    cout.tie(0), cin.tie(0);

    if (fopen("input.txt", "r")) {
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    }

    int _t = 1;
    // cin >> _t;
    while (_t--) {
        solve();
    }
}

Compilation message (stderr)

xor.cpp: In function 'int main()':
xor.cpp:93:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |         freopen("input.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
xor.cpp:94:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |         freopen("output.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100