제출 #1192379

#제출 시각아이디문제언어결과실행 시간메모리
1192379mk72XOR (IZhO12_xor)C++20
100 / 100
108 ms56660 KiB
#include <bits/stdc++.h> using namespace std; #define endl "\n" #define ll long long #define all(x) x.begin(), x.end() #define siz(x) (int)(x.size()) void Mk72(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); } class Trie{ private: struct Node{ Node* nxt[2]{}; int prefix; int idx; Node(){ memset(nxt, 0, sizeof nxt); prefix = 0; idx = 1e7; } }; Node* root = new Node(); public: void insert(const int& x, const int& i){ Node* cur = root; for(int j = 30; j >= 0; --j){ int idx = (x >> j) & 1; if(cur->nxt[idx] == nullptr) cur->nxt[idx] = new Node(); cur = cur->nxt[idx]; cur->idx = min(i, cur->idx); } } int answer(const int& x, const int& k){ Node* cur = root; int mn = 1e7; for(int j = 30; j >= 0; --j){ int idx = (k >> j) & 1; int i = (x >> j) & 1; if(!idx){ if(cur->nxt[i ^ 1] != nullptr) mn = min(mn, cur->nxt[i ^ 1]->idx); } if(cur->nxt[i ^ idx] == nullptr) return mn; cur = cur->nxt[i ^ idx]; } return min(mn, cur->idx); } }; void solve() { int n, k; cin >> n >> k; Trie tr; tr.insert(0, 0); int x = 0; ll ans = 0, idx; for(int i = 1; i <= n; ++i){ int a; cin >> a; x ^= a; tr.insert(x, i); a = tr.answer(x, k); if(i - a > ans){ ans = i - a; idx = a + 1; } } cout << idx << ' ' << ans << endl; } // Don't forget check it take test case int main() { Mk72(); int T = 1; //cin >> T; while (T--) { solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...