Submission #1307705

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307705		mosaab	XOR (IZhO12_xor)	C++17	0 / 100	1 ms	332 KiB

xor

// عَجَبًا لأَمْرِ المُؤْمِنِ، إنَّ أمْرَهُ كُلَّهُ خَيْرٌ
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const char el = '\n';

struct Trie {
    Trie *p[2]{};
    int mn{1000000000}, lz{}, i{};

    void prp() {
        if (lz >> i & 1)
            swap(p[0], p[1]);
        if (p[0]) p[0]->lz ^= lz;
        if (p[1]) p[1]->lz ^= lz;
        lz = 0;
    }

    void insert(int x, int idx) {
        prp();
        mn = min(mn, idx);
        if (i == -1) return;
        if (x >> i & 1) {
            if (!p[1]) p[1] = new Trie(), p[1]->i = i - 1;
            p[1]->insert(x, idx);
        } else {
            if (!p[0]) p[0] = new Trie(), p[0]->i = i - 1;
            p[0]->insert(x, idx);
        }
    }

    int query(int l) {
        prp();
        if (i == -1) return mn;
        int ans = 1000000000;
        if (l >> i & 1)
            return p[1] ? p[1]->query(l) : ans;
        if (p[1]) ans = min(ans, p[1]->mn);
        if (p[0]) ans = min(ans, p[0]->query(l));
        return ans;
    }
};

void unsolve() {
    int n, x;
    cin >> n >> x;
    Trie s;
    s.i = 30;
    s.insert(0, 0);
    int len = 0, idx = 0;
    for (int i = 1, v, xr = 0; i <= n; i++) {
        cin >> v;
        xr ^= v;
        s.insert(xr, i);
        s.lz ^= xr;
        int q = s.query(x);
        s.lz ^= xr;
        if (i - q > len) {
            len = i - q;
            idx = q + 1;
        }
    }
    cout << idx << ' ' << len;
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
#if Mosaab
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
    freopen("c.in", "r", stdin);
    freopen("c.out", "w", stdout);
#endif
    int t = 1;
    // cin >> t;
    while (t--) unsolve(), cout << el;
}

Compilation message (stderr)

xor.cpp: In function 'int main()':
xor.cpp:72:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |     freopen("c.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~
xor.cpp:73:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |     freopen("c.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100