Submission #1275931

#TimeUsernameProblemLanguageResultExecution timeMemory
1275931anarch_yXOR (IZhO12_xor)C++20
100 / 100
113 ms25268 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define all(x) begin(x), end(x) #define sz(x) (int)x.size() #define pb push_back struct Trie{ static const int wmax = 6e6+1; int trie[wmax][2]; int mn[wmax]; bool stop[wmax]; int num; void insert(int x, int j){ int cur = 0; for(int i=30; i>=0; i--){ bool c = x & (1<<i); if(trie[cur][c] == 0){ trie[cur][c] = ++num; } cur = trie[cur][c]; } if(!stop[cur]){ stop[cur] = true; mn[cur] = j; } } void dfs(int cur){ if(stop[cur]) return; mn[cur] = 1e9; for(int c=0; c<2; c++){ if(trie[cur][c]){ dfs(trie[cur][c]); mn[cur] = min(mn[cur], mn[trie[cur][c]]); } } } int find(int m, int x){ int cur = 0; int ans = 1e9; for(int i=30; i>=0; i--){ bool c = m & (1<<i); bool d = x & (1<<i); if(c == 0){ if(d == 0){ if(trie[cur][1]){ ans = min(ans, mn[trie[cur][1]]); } if(trie[cur][0]) cur = trie[cur][0]; else break; } else{ if(trie[cur][1]) cur = trie[cur][1]; else break; } } else{ if(d == 0){ if(trie[cur][0]){ ans = min(ans, mn[trie[cur][0]]); } if(trie[cur][1]) cur = trie[cur][1]; else break; } else{ if(trie[cur][0]) cur = trie[cur][0]; else break; } } } return ans; } }; Trie T; int main(){ ios::sync_with_stdio(0); cin.tie(0); int n, x; cin >> n >> x; vector<int> a(n+1); for(int i=1; i<=n; i++) cin >> a[i]; if(x == 0){ cout << 1 << ' ' << n; return 0; } x--; vector<int> p(n+1); T.insert(0, 0); for(int i=1; i<=n; i++){ p[i] = (a[i]^p[i-1]); T.insert(p[i], i); } T.dfs(0); int k = 0; for(int i=1; i<=n; i++){ int j = T.find(p[i], x); if(j < i){ k = max(k, i-j); } } for(int i=1; i+k-1<=n; i++){ if((p[i+k-1]^p[i-1]) > x){ cout << i << ' ' << k; return 0; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...