Submission #558841

#	Time	Username	Problem	Language	Result	Execution time	Memory
558841		KiriLL1ca	XOR (IZhO12_xor)	C++14	100 / 100	165 ms	93336 KiB

xor

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fr first
#define sc second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pw(x) (1ll << x)
#define sz(x) (int)((x).size())
#define pb push_back
#define endl '\n'
#define vec vector
 
using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
 
template <typename T> inline bool umin (T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }
template <typename T> inline bool umax (T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
 
template <typename T>
using oset = tree<T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
 
const int N = 250010;
const int lg = 31;
 
int go[N * lg][2], link = 0;
int vl[N * lg];
 
inline void add (int x, int p) {
      int f = 0;
      for (int i = lg; ~i; --i) {
            int bt = (x >> i & 1);
            if (!~go[f][bt]) go[f][bt] = ++link;
            f = go[f][bt];
            umin(vl[f], p);
      }
}
inline int get (int p, int x) {
      int f = 0, res = 1e9;
      for (int i = lg; ~i; --i) {
            int bt1 = (p >> i & 1);
            int bt2 = (x >> i & 1);
            if (!bt2 && ~go[f][bt1 ^ 1]) umin(res, vl[go[f][bt1 ^ 1]]);
            if (!~go[f][bt1 ^ bt2]) return res;
            f = go[f][bt1 ^ bt2];
      }
      return min(res, vl[f]);
}
 
inline void solve () {
      for (int i = 0; i < N * lg; ++i) { go[i][0] = go[i][1] = -1; vl[i] = 1e9; }
      int n, x; cin >> n >> x; add(0, 0);
      int ans = 0, pos = 0, px = 0;
      for (int i = 1; i <= n; ++i) {
            int y; cin >> y; px ^= y;
            int k = get(px, x);
            if (umax(ans, i - k)) pos = k + 1;
            add(px, i);
      }
      cout << pos << " " << ans << endl;
}
 
signed main() {
      ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
      int t = 1; //cin >> t;
      while (t--) solve();
      return 0;
}

• Subtask 1: 100 / 100