제출 #1336121

#제출 시각아이디문제언어결과실행 시간메모리
1336121cseguraXOR (IZhO12_xor)C++20
100 / 100
353 ms121600 KiB
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;

#define optimizar_io ios_base::sync_with_stdio(0);cin.tie(0);
typedef pair<int, int>             pii;
typedef pair<long long, int>       pli;
typedef pair<pii, int>              piii;
typedef pair<long long, long long> pll;
typedef pair<pll, long long>        plll;
typedef vector<int>                vi;
typedef vector<bool>                vb;
typedef vector<vector<bool>>        vvb;
typedef vector<char>                vc;
typedef vector<vector<int>>        vvi;
typedef vector<long long>          vl;
typedef vector<vector<char>>       vvc;
typedef vector<vector<long long>>  vvl;
typedef vector<pii>                vpii;
typedef vector<piii>               vpiii;
typedef vector<pli>                vpli;
typedef vector<pll>                vpll;
typedef vector<plll>               vplll;
typedef vector<vector<plll>>       vvplll;
typedef vector<vector<pll>>        vvpll;
typedef vector<vector<piii>>       vvpiii;
typedef vector<vector<pii>>        vvpii;
typedef vector<vector<pli>>        vvpli;
typedef long long                  ll;

using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define data data_
#define endl "\n"
#define isOn(S, j) ((S) & (1ll << (j)))
#define setBit(S, j) ((S) |= (1ll << (j)))
#define clearBit(S, j) ((S) &= ~(1ll << (j)))
#define toggleBit(S, j) (S ^= (1ll << (j)))
#define bzero(b,len) (memset((b), '\0', (len)), (void) 0)
#define all(x) x.begin(),x.end()
#define sz(x) x.size()
#define dbg(v) cout << "Line(" << __LINE__ << ") -> " << #v << " = " << (v) << endl

class Trie{
	public:
		Trie(){
			words = 0;
			min_idx = INT_MAX;
		}
		
		void insert(const string &s, int from, int idx){
			words++;
			if (from != s.size()){
				if (child.size() == 0) child.resize(2);
				child[s[from]-'0'].insert(s, from + 1, idx);
				min_idx = min(min_idx, child[s[from]-'0'].min_idx);
			} else {
				min_idx = min(min_idx, idx);
			}
		}

		//Cuantos numeros hay tales que la porción que queda
		//del número v (desde from) al hacer xor con ellos
		//sea menor que la parte correspondiente de k
		int minIdxXORvHigherK(int v, int from, int k){
			if (from == 30) return INT_MAX;
			if (words == 0) return INT_MAX;
			int bit_v = (isOn(v, 29-from)?1:0);
			int bit_k = (isOn(k, 29-from)?1:0);
			int ans = INT_MAX;
			if (bit_k == 0){
				ans = min(ans, child[1-bit_v].min_idx);
				ans = min(ans, child[bit_v].minIdxXORvHigherK(v, from + 1, k));
			} else {
				ans = min(ans, child[1-bit_v].minIdxXORvHigherK(v, from + 1, k));
			}
			return ans;
		}

		vector<Trie> child;
		int words;
		int min_idx;
};

int main(){
	optimizar_io;
	Trie trie;
	int n, x; cin >> n >> x; x--; //Must be greater than x
	int acXor = 0;
	trie.insert(bitset<30>(0).to_string(), 0, 0);
	long long res = 0;
	int max_dist = -1, init = -1;
	for (int i = 0; i < n; i++){
		int v; cin >> v;
		acXor ^= v;
		string acXor_str = bitset<30>(acXor).to_string();
		int init_idx = trie.minIdxXORvHigherK(acXor, 0, x);
		int len = -1;
		if (init_idx != INT_MAX) len = (i - init_idx + 1);
		if (len > max_dist){
			max_dist = len;
			init = init_idx + 1;
		}
		trie.insert(acXor_str, 0, i + 1);
	}
	cout << init << " " << max_dist << endl;
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...