Submission #1184730

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

xor

#include <complex.h>
#include<bits/stdc++.h>
using namespace std;
#define Hassouna std::ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
#define all(c) (c).begin(),(c).end()
const long long N = 2e5 + 5, M = 1e9 + 7, OO = 0x3f3f3f3, mod = 1e9 + 7, Log = 30;
#define Count(s,a) (std::count((s).begin(), (s).end(),(a)))
int dx[] = {1, 0, -1, 0, -1, -1, 0, 1};
int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
string D[] = {"D", "R", "U", "L", "RD", "LD", "RU", "LU"};
#define ll long long
#define ii pair<int,int>
#define getBit(x,n) (x & (1LL << n))
#define TogBit(x,n) ((x)^=(1LL<<(n)))

int n, k;

struct Trie
{
    struct Node
    {
        Node* ch[2];
        int Min;

        Node()
        {
            Min = 1e7;
            ch[0] = ch[1] = nullptr;
        }
    };

    Node* root = new Node();

    void insert(int x, int idx)
    {
        Node* cur = root;
        for (int j = Log; j >= 0; j--)
        {
            int bit = bool(getBit(x, j));
            if (!cur->ch[bit])
            {
                cur->ch[bit] = new Node();
            }
            cur = cur->ch[bit];
            cur->Min = min(cur->Min, idx);
        }
    }


    int search(int x)
    {
        Node* cur = root;
        int i = -1;
        for (int j = Log; j >= 0; j--)
        {
            int bitk = bool(getBit(k, j));
            int bitx = bool(getBit(x, j));

            if (!bitk)
            {
                if (cur->ch[1 - bitx] != nullptr)
                {
                    i = min(i, cur->ch[1 - bitx]->Min);
                }
                cur = cur->ch[bitx];
            }
            else
            {
                if (cur->ch[1 - bitx] != nullptr)
                    cur = cur->ch[1 - bitx];
                else break;
            }
            if (cur == nullptr)break;
        }
        return i;
    }
};

int main()
{
    Hassouna
    cin >> n >> k;
    int A[n + 1];
    for (int i = 1; i <= n; i++) cin >> A[i];
    for (int i = 1; i <= n; i++) A[i] = (A[i] ^ A[i - 1]);

    map<int, int> Freq;
    Trie trie;
    int ans = 0, idx = 0;
    for (int j = 1; j <= n; j++)
    {
        if (Freq.count(A[j]) == 0)Freq[A[j]] = j;

        int eq = 0;
        if (Freq.count(A[j] ^ k))
        {
            eq = j - Freq[A[j] ^ k] + 1;
            if (eq > ans)
            {
                idx = Freq[A[j] ^ k];
            }
        }

        int val = trie.search(A[j]), big = 0;
        if (val != -1)big = j - val + 1;
        if (big > ans)
        {
            idx = val;
        }

        ans = max({ans, eq, big});
        trie.insert(A[j], j);
    }
    if (ans==0)
    {
        cout << "1 0";
    }else
    {
        cout << idx <<  ' ' << ans;
    }
}

• Subtask 1: 0 / 100