Submission #1281724

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281724		hashirama__	XOR (IZhO12_xor)	C++20	0 / 100	210 ms	327680 KiB

xor

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define all(v) v.begin(),v.end()
void file() { if (fopen("in.txt", "r")) { freopen("in.txt", "r", stdin), freopen("out.txt", "w", stdout); } }

struct Bnode {
    int ch[2] = {}, freq = 0, j = 1e9;
    int& operator[](int x) {
        return ch[x];
    }
};
struct Binary_Trie {
    vector<Bnode> tr;
    const int M = 32;
    Binary_Trie() {
        newNode();
    }
    int newNode() {
        tr.emplace_back();
        return tr.size() - 1;
    }
    void update(int x, int op, int indx) {
        int u = 0;
        for (int i = M - 1; i >= 0; i--) {
            int bit = x >> i & 1;
            if (!tr[u][bit]) tr[u][bit] = newNode();
            u = tr[u][bit];
            tr[u].j = min(tr[u].j, indx);
            tr[u].freq += op;
        }
    }
    int sz(int u) {
        return tr[u].freq;
    }

    int solve(int pR, int x) {
        int u = 0, res = 1e9 + 12;
        for (int i = M - 1; i >= 0; --i) {
            int bitR = pR >> i & 1, bitX = x >> i & 1;
            int go = bitR ^ bitX;
            if (!bitX) {
                res = min(tr[tr[u][!bitR]].j, res);
            }
            u = tr[u][go];
            if (!u) return res;
        }
        return min(res, tr[u].j);
    }
};
int32_t main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); 
    // file();
    freopen("c.txt", "r", stdin), freopen("c.txt", "w", stdout); 
    int n, x;
    cin >> n >> x;
    int ar[n + 1] = {};
    for (int i = 1; i <= n; i++) cin >> ar[i], ar[i] ^= ar[i - 1];
    Binary_Trie trie;
    trie.update(0, +1, 0);
    int indx = -1, len = n + 1;
    for (int r = 1; r <= n; r++) {
        int Pl = trie.solve(ar[r], x);
        if (len > Pl) {
            len = r - Pl;
            indx = Pl + 1;
        }
        else if (len == Pl) {
            indx = min(indx, Pl + 1);
        }
        trie.update(ar[r], +1, r);
    }
    cout << indx << " " << len << endl;
}

Compilation message (stderr)

xor.cpp: In function 'void file()':
xor.cpp:6:50: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    6 | void file() { if (fopen("in.txt", "r")) { freopen("in.txt", "r", stdin), freopen("out.txt", "w", stdout); } }
      |                                           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
xor.cpp:6:81: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    6 | void file() { if (fopen("in.txt", "r")) { freopen("in.txt", "r", stdin), freopen("out.txt", "w", stdout); } }
      |                                                                          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
xor.cpp: In function 'int32_t main()':
xor.cpp:55:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |     freopen("c.txt", "r", stdin), freopen("c.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
xor.cpp:55:42: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |     freopen("c.txt", "r", stdin), freopen("c.txt", "w", stdout);
      |                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100