Submission #1196721

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196721		m_elgamal	XOR (IZhO12_xor)	C++17	0 / 100	1 ms	320 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;
map<ll, int> eq;
vector<array<int, 2>> id(64);
class BinaryTrie
{
private:
    struct Node
    {
        Node* ch[2];
        int fr;
        Node() : fr(0) {
            memset(ch, 0, sizeof ch);
        }
    };

public:
    Node* root = new Node();
    BinaryTrie() { insert(0); }
    void insert(ll x) {
        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++;
        }
    }
    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 mn = 66;
        for (int i = 62; i >= 0; i--) {
            int xb = (x >> i) & 1, yb = (y >> i) & 1;

            if (xb == 0 && cur->ch[!yb]) 
                mn = min(mn, id[i][!yb] + 1);
                
            xb ^= yb;
            if (!cur->ch[xb])
                return mn;
            cur = cur->ch[xb];
        }
        x ^= y;
        return min(mn, eq[x] + 1);
    }
};
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;
        eq[pre] = (eq.count(pre) ? eq[pre] : i);

        for (int j = 0; j < 63; j++)
            if ((pre >> j) & 1)
                id[j][1] = (!id[j][1] ? i : id[j][1]);
            else
                id[j][0] = (!id[j][0] ? i : id[j][0]);

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

        trie.insert(pre);
    }
    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:98:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |         freopen("input.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
xor.cpp:99:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |         freopen("output.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100