제출 #1130822

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1130822		amigoo	XOR (IZhO12_xor)	C++17	0 / 100	1 ms	324 KiB

xor

#include <bits/stdc++.h>

using namespace std;

const long long MOD = 1e9 + 7;
// const long long MOD = 998244353;

#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)

#define popCnt(x) (__builtin_popcountll(x))
#define int long long

#define F  first
#define S  second
#define double long double
#define pi  M_PI
#define all(x) x.begin() , x.end()
#define ll long long

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
const long long OO = 1e9, N = 2e5 + 5;

int k;

struct Trie {
    Trie *link[2];
    int cnt;
    int leaf;
    int mn;

    Trie() {
        for (int i = 0; i < 2; ++i) {
            link[i] = nullptr;
        }
        cnt = 0;
        leaf = 0;
        mn = OO;
    }

    void insert(int x, int i, int idx = 30) {
        if (idx == -1) {
            cnt++;
            leaf++;
            mn = min(mn, i);
            return;
        }
        bool ch = ((1ll << idx) & x);
        if (link[ch] == nullptr)link[ch] = new Trie();
        link[ch]->insert(x, i, idx - 1);
        mn = min(mn, i);
        cnt++;
    }

    bool erase(int x, int idx = 30) {
        if (idx == -1) {
            cnt--;
            leaf--;
            return true;
        }

        bool ch = ((1ll << idx) & x);
        if (link[ch] == nullptr) {
            return false;
        }
        if (link[ch]->erase(x, idx - 1)) {
            cnt--;
            if (link[ch]->cnt == 0) {
                delete link[ch];
                link[ch] = nullptr;
            }
            return true;
        }
        return false;
    }

    int find(int x, int idx = 30) {
        if (idx == -1)return cnt;

        bool ch = ((1ll << idx) & x);
        if (link[ch] == nullptr)return 0;
        return link[ch]->find(x, idx - 1);
    }

    int MinXor(int x, int idx = 30) {
        if (idx == -1) {
            return 0;
        }

        bool ch = ((1ll << idx) & x);

        if (link[ch] != nullptr) {
            return link[ch]->MinXor(x, idx - 1);
        } else if (link[!ch] != nullptr)return link[!ch]->MinXor(x, idx - 1) | (1ll << idx);
        return x;
    }

    int Query(int x, int idx = 30) {
        if (idx == -1)return OO;

        bool cur = ((1ll << idx) & x);
        bool target = ((1ll << idx) & k);

        if (cur == target) {
            int temp = OO;
            if (cur == 0 && link[1] != nullptr)temp = link[1]->mn;
            if (link[0] == nullptr)return temp;
            return min(link[0]->Query(x, idx - 1), temp);
        } else if (cur == 1) {
            int temp = OO;
            if (link[0] != nullptr)temp = link[0]->mn;
            if (link[1] == nullptr)return temp;
            return min(link[1]->Query(x, idx - 1), temp);
        } else if (cur == 0) {
            int temp = OO;
            if (link[1] == nullptr)return temp;
            return min(link[1]->Query(x, idx - 1), temp);
        }
        return OO;
    }
};

signed main() {
    fast;

    int t = 1;
//    cin >> t;
    for (int tct = 1; tct <= t; tct++) {


        int n;
        cin >> n >> k;
        Trie tr;
        tr.insert(0, 0);
        int a[n], pre[n];

        pair<int, int> ans = {-1, -1};
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
            if (!i)pre[i] = a[i];
            else pre[i] = pre[i - 1] ^ a[i];


            int j = tr.Query(pre[i]);
            if(j != OO)
            {
                if ((i - j + 1) > ans.F) ans = {i - j + 1, j} ;
                else if ((i - j + 1 == ans.F) && j < ans.S)  ans = {i - j + 1, j};
            }


            tr.insert(pre[i], i + 1);

        }
        cout << ans.second + 1 << " " << ans.first << endl;


    }
}

// 111
// 110

// 101

• Subtask 1: 0 / 100