oj.uz

Submission #558841

# Submission time Handle Problem Language Result Execution time Memory
558841 2022-05-08T16:12:39 Z KiriLL1ca XOR (IZhO12_xor) C++14
100 / 100
 165 ms 93336 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 91220 KB Output is correct
2 Correct 54 ms 91312 KB Output is correct
3 Correct 57 ms 91188 KB Output is correct
4 Correct 42 ms 91248 KB Output is correct
5 Correct 47 ms 91404 KB Output is correct
6 Correct 50 ms 91456 KB Output is correct
7 Correct 56 ms 91412 KB Output is correct
8 Correct 53 ms 91444 KB Output is correct
9 Correct 96 ms 91980 KB Output is correct
10 Correct 88 ms 92064 KB Output is correct
11 Correct 72 ms 92192 KB Output is correct
12 Correct 75 ms 92056 KB Output is correct
13 Correct 76 ms 92060 KB Output is correct
14 Correct 82 ms 91980 KB Output is correct
15 Correct 78 ms 92056 KB Output is correct
16 Correct 72 ms 91968 KB Output is correct
17 Correct 145 ms 93216 KB Output is correct
18 Correct 163 ms 93236 KB Output is correct
19 Correct 165 ms 93212 KB Output is correct
20 Correct 135 ms 93336 KB Output is correct