Submission #558785

#	Time	Username	Problem	Language	Result	Execution time	Memory
558785		KiriLL1ca	XOR (IZhO12_xor)	C++17	0 / 100	55 ms	121644 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][2];

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;
            umin(vl[f][bt], p);
            f = go[f][bt];
      }
}
inline int get (int x) {
      int f = 0, res = 1e9;
      for (int i = lg; ~i; --i) {
            int bt = (x >> i & 1);
            if (~go[f][bt ^ 1]) umin(res, vl[f][bt ^ 1]);
            if (!~go[f][bt]) break;
            f = go[f][bt];
      }
      return res;
}

inline void solve () {
      for (int i = 0; i < N * lg; ++i) { go[i][0] = go[i][1] = -1; vl[i][0] = vl[i][1] = 1e9; }
      int n, x; cin >> n >> x;
      int ans = 0, pos = 0, px = 0;
      for (int i = 0; i < n; ++i) {
            int y; cin >> y; px ^= y;
            add(px, i); int k = get(x);
            if (umax(ans, i - k + 1)) pos = k;
      }
      cout << pos + 1 << " " << 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: 0 / 100