| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 869763 |
2023-11-05T14:31:50 Z |
Firas_Briki |
XOR (IZhO12_xor) |
C++17 |
|
217 ms |
101756 KB |
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace std;
using namespace __gnu_pbds;
// #ifndef ONLINE_JUDGE
// #include "debug.cpp"
// #else
// #define dbg(...)
// #endif
#define endl "\n"
#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL);
#define ll long long
#define pb(n) push_back(n)
#define F first
#define S second
#define mp(x, y) make_pair(x, y)
#define yes cout << "YES" << endl;
#define no cout << "NO" << endl;
#define nop cout << -1 << endl;
#define ordered_set tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update>
const ll sup = 1e18;
const ll inf = -1e18;
const ll mod = 1e9 + 7;
const int N_Max = 3e5 + 7;
const int Nax = 15;
const int LOG = 18;
const int BITS = 30;
const int ALPHA = 26;
ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a;}
ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);}
ll inv(ll N) {if (N == 1) return 1; return (mod - ((mod / N) * inv(mod % N)) % mod) % mod;}
int nxt[30 * N_Max][2], mn[30 * N_Max][2];
int a[N_Max], pref[N_Max];
map<int, int> mp;
int N, x, cnt = 1;
int nxt_node(){
return ++cnt;
}
void ins(int val, int ind){
int curr = 1;
for (int i = 30; i >= 0; i--){
int c = (val >> i) & 1;
if (nxt[curr][c] == -1){
mn[curr][c] = ind;
nxt[curr][c] = nxt_node();
}
mn[curr][c] = min(mn[curr][c], ind);
curr = nxt[curr][c];
}
}
int query(int val){
int ret = 2e9, curr = 1;
for (int i = 30; i >= 0; i--){
if (curr == -1) break;
int c = (val >> i) & 1, v = (x >> i) & 1;
if (!v && nxt[curr][c ^ 1] != -1)
ret = min(ret, mn[curr][c ^ 1]);
if (v) curr = nxt[curr][c ^ 1];
else curr = nxt[curr][c];
}
return ret;
}
void solve(){
cin >> N >> x;
memset(nxt, -1, sizeof(nxt));
for (int i = 1; i <= N; i++) cin >> a[i];
for (int i = 1; i <= N; i++) pref[i] = pref[i - 1] ^ a[i];
pair<int, int> ans = {0, 0};
for (int r = 1; r <= N; r++){
ins(pref[r - 1], r);
if (!mp.count(pref[r - 1])) mp[pref[r - 1]] = r;
int l = query(pref[r]), val = x ^ pref[r];
if (mp.count(val)) l = min(l, mp[val]);
if (l == 2e9) continue;
if (r - l + 1 > ans.S) ans = {l, r - l + 1};
else if (r - l + 1 == ans.S) ans.F = min(ans.F, l);
}
assert(ans.F != 0);
cout << ans.F << " " << ans.S << endl;
}
int main(){
FAST
// #ifndef ONLINE_JUDGE
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
// #endif
int tc = 1;
// cin >> tc;
while (tc--) solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
75612 KB |
Output is correct |
| 2 |
Correct |
9 ms |
75724 KB |
Output is correct |
| 3 |
Correct |
9 ms |
75612 KB |
Output is correct |
| 4 |
Correct |
10 ms |
75816 KB |
Output is correct |
| 5 |
Correct |
18 ms |
76636 KB |
Output is correct |
| 6 |
Correct |
21 ms |
76752 KB |
Output is correct |
| 7 |
Correct |
22 ms |
76904 KB |
Output is correct |
| 8 |
Correct |
22 ms |
76940 KB |
Output is correct |
| 9 |
Correct |
72 ms |
87316 KB |
Output is correct |
| 10 |
Correct |
68 ms |
87380 KB |
Output is correct |
| 11 |
Correct |
68 ms |
87456 KB |
Output is correct |
| 12 |
Correct |
68 ms |
87368 KB |
Output is correct |
| 13 |
Correct |
67 ms |
87380 KB |
Output is correct |
| 14 |
Correct |
69 ms |
87380 KB |
Output is correct |
| 15 |
Correct |
69 ms |
87376 KB |
Output is correct |
| 16 |
Correct |
67 ms |
87440 KB |
Output is correct |
| 17 |
Correct |
217 ms |
101628 KB |
Output is correct |
| 18 |
Correct |
216 ms |
101756 KB |
Output is correct |
| 19 |
Correct |
217 ms |
101708 KB |
Output is correct |
| 20 |
Correct |
211 ms |
101716 KB |
Output is correct |
