Submission #869764

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
869764	2023-11-05T14:32:41 Z	Firas_Briki	XOR (IZhO12_xor)	C++17	100 / 100	85 ms	88264 KB

xor

#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];
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;
	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);
		int l = query(pref[r]);
		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;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	75612 KB	Output is correct
2	Correct	9 ms	75808 KB	Output is correct
3	Correct	9 ms	75612 KB	Output is correct
4	Correct	10 ms	75780 KB	Output is correct
5	Correct	12 ms	75864 KB	Output is correct
6	Correct	15 ms	75860 KB	Output is correct
7	Correct	14 ms	75812 KB	Output is correct
8	Correct	15 ms	75808 KB	Output is correct
9	Correct	29 ms	82000 KB	Output is correct
10	Correct	30 ms	81876 KB	Output is correct
11	Correct	29 ms	82136 KB	Output is correct
12	Correct	28 ms	82144 KB	Output is correct
13	Correct	29 ms	82140 KB	Output is correct
14	Correct	30 ms	82004 KB	Output is correct
15	Correct	29 ms	81876 KB	Output is correct
16	Correct	28 ms	82012 KB	Output is correct
17	Correct	75 ms	88148 KB	Output is correct
18	Correct	85 ms	88264 KB	Output is correct
19	Correct	72 ms	88148 KB	Output is correct
20	Correct	70 ms	88092 KB	Output is correct