제출 #1325843

#제출 시각아이디문제언어결과실행 시간메모리
1325843ray.1XOR (IZhO12_xor)C++20
0 / 100
1 ms332 KiB
#include <iostream>
#include <iomanip>
#include <vector>
#include <array>
#include <algorithm>
#include <string>
#include <cmath>
#include <sstream>
#include <set>
#include <map>
#include <unordered_map>
#include <stack>
#include <queue>
#include <list>
#include <functional>
#include <numeric>
using namespace std;
#define int long long
const int inf = 1e15;
int MAX = 1000005;
const int N = 31;
struct node {
    int adj[2]{};
    int &operator[](int i) { return adj[i]; }
};

struct Trie {
    vector<node> trie;

    int newnode() {
        trie.emplace_back();
        return trie.size() - 1;
    }

    void init() {
        newnode();
    }

    int update(int val) {
        int u = 0;
        for (int i = N-1; ~i; i--) {
            int v = (val >> i) & 1;
            if (!trie[u][v]) {
                trie[u][v] = newnode();
            }
            u = trie[u][v];
        }

        u = 0;
        int ans{};
        for (int i = N-1; ~i; i--) {
            int v = (val >> i)& 1;
            if (trie[u][!v]) {
                u = trie[u][!v];
            }
            else {
                u = trie[u][v];
                ans += (1ll << i);
            }
        }
        return ans;
    }
};


void solve() {
    int n, x, Xor{}; cin >> n >> x;
    vector<int> v(n);
    Trie t;
    t.init();
    t.update(0);
    map<int, int> mp;
    mp[0] = -1;
    array<int, 3> ans{};
    for (int i = 0; i < n; i++) {
        cin >> v[i];
        Xor ^= v[i];
        if (!mp.count(v[i])) {
            mp[v[i]] = i;
        }

        int tmp = t.update(v[i]);
        if (Xor ^ tmp > ans[0] and Xor ^ tmp >= x) {
            if (Xor ^ tmp == ans[0] and ans[2] > i - mp[tmp]) continue;
            ans[0] = Xor ^ tmp;
            ans[1] = mp[tmp] + 1;
            ans[2] = i - mp[tmp] + 1;
        }
    }

    cout << ans[1] + 1 << ' ' << ans[2] << '\n';
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    for (int i = 1; i <= t; i++) {
        solve();
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...