Submission #1224753

#TimeUsernameProblemLanguageResultExecution timeMemory
1224753tkm_algorithmsXOR (IZhO12_xor)C++20
0 / 100
1 ms320 KiB
/** * In the name of Allah * We are nothing and you're everything * Ya Muhammad! **/ #include <bits/stdc++.h> using namespace std; using ll = long long; using ull = uint64_t; #define all(x) begin(x), end(x) #define sz(x) (int)(x).size() //#define int long long const char nl = '\n'; const int N = 2e5+5; const int LOG = 30; const ll inf = 0x3f3f3f3f3f3f3f3fll; int tree[N*LOG][2]; int ind; int mn[N*LOG][2], par[N*LOG][2]; void add(int x, int j) { int cur = 0; for (int i = LOG-1; i >= 0; --i) { int bit = (x>>i)&1; if (!tree[cur][bit]) { tree[cur][bit] = ++ind; mn[tree[cur][bit]][bit] = j; } cur = tree[cur][bit]; } } int get(int x) { int res = N; int cur = 0; int last = 0; for (int i = LOG-1; i >= 0; --i) { int bit = (x>>i)&1; last = bit; if (bit == 1) { if (!tree[cur][bit])return res; } else { if (tree[cur][1] > 0)res = min(res, mn[tree[cur][1]][1]); if (!tree[cur][bit])return res; } if (x == 0 && res == 1)cout << i << nl; if (i == 0)res = min(res, mn[tree[cur][bit]][bit]); cur = tree[cur][bit]; } //res = min(res, mn[cur][last]); return res; } void solve() { int n, x; cin >> n >> x; add(0, 0); int xx = 0; int ans = -1, ans2; for (int i = 1; i <= n; ++i) { int a; cin >> a; xx ^= a; int val = get(x^xx); if (xx >= x) { if (i > ans)ans = i, ans2 = 1; } //if (i == 1)cout << val << nl; if (i-val > ans) { //cout << val << nl; //cout << xx << nl; ans = i-val; ans2 = val+1; } add(xx, i); } if (ans == -1)cout << "-1"; else cout << ans2 << " " << ans; } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...