Submission #558838

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
558838	2022-05-08T16:01:11 Z	KiriLL1ca	XOR (IZhO12_xor)	C++14	0 / 100	5 ms	9044 KB

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 = 3;

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[link], 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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	5 ms	9044 KB	Output isn't correct
2	Halted	0 ms	0 KB	-