Submission #1235099

#TimeUsernameProblemLanguageResultExecution timeMemory
1235099mazenxvXOR (IZhO12_xor)C++20
100 / 100
175 ms86700 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define int long long #define all(v) v.begin(), v.end() #define allr(v) v.rbegin(), v.rend() #define F first #define S second #define P push_back #define endl '\n' #define pqmn pi , vector<pi> , greater<pi> const int N = 1e6 + 10; const int R = 5e3 + 10; const int mod = 1e9 + 7; const int inf = 1e9 + 10; const ll infll = 1e17; typedef pair<int, int> pi; typedef vector<int> vi; typedef vector<pi> vii; typedef vector<vi> vvi; typedef vector<vii> vvii; const int CHAR = 2; const int LOG = 32; int p[LOG]; struct trie { trie* child[CHAR]; int cnt; int ind; trie(int f) { memset(child, 0, sizeof child); cnt = 0; for(int i = 0 , po = 1 ; i < LOG ; i++ , po <<= 1) p[i] = po; } trie() { memset(child, 0, sizeof child); cnt = 0; ind = 0; } void insert(int x , int ind ,int i = LOG-1) { cnt++; this->ind = max(this->ind , ind); if (i == -1) return; int cur = (x&p[i]) > 0; if (child[cur] == 0) child[cur] = new trie(); child[cur]->insert(x, ind ,i-1); } int Xor(int x , int s , int val , int i = LOG - 1) { if(s >= val) return this->ind; if(i == -1 and s < val) return -inf; if(i == -1 and s >= val) return this->ind; int ans = -inf; if(val & p[i]){ int cur = ((x ^ p[i]) & p[i]) > 0; if(child[cur]) ans = max(ans , child[cur]->Xor(x , s | p[i] , val , i - 1)); } else{ int cur = ((x ^ p[i]) & p[i]) > 0; if(child[cur]) ans = max(ans , child[cur]->Xor(x , s | p[i] , val , i - 1)); if(child[!cur]) ans = max(ans , child[!cur]->Xor(x , s , val , i - 1)); } return ans; } }; int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n , x; cin >> n >> x; auto R = new trie(0); vi preXor(n + 1); for(int i = 1 ; i <= n ; i++){ cin >> preXor[i]; preXor[i] = preXor[i] ^ preXor[i - 1]; } int ind , k = 0; for(int i = n ; i >= 1 ; i--){ R->insert(preXor[i] , i); int idx = R->Xor(preXor[i - 1] , 0 , x); if(idx - i + 1 >= k){ ind = i; k = idx - i + 1; } } cout << ind << " " << k << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...