# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
58113 |
2018-07-16T21:15:47 Z |
Benq |
XOR (IZhO12_xor) |
C++14 |
|
170 ms |
29392 KB |
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 250001;
int n,x,cum[MX];
template<int MX> struct tri {
static const int MXBIT = 30;
int trie[MX][2], mn[MX], nex = 0; // easily changed to character
void ins(int ind, int a = 1) { // insert or delete
int x = cum[ind];
int cur = 0;
F0Rd(i,MXBIT) {
int t = (x&(1LL<<i))>>i;
if (!trie[cur][t]) {
trie[cur][t] = ++nex;
mn[nex] = ind;
trie[nex][0] = trie[nex][1] = 0;
}
cur = trie[cur][t];
}
}
int test(int num, int cur = 0, int cbit = 29, int z = 0) {
if (cur == 0 && cbit != 29) return MOD;
if (z || cbit == -1) return mn[cur];
int b = (num>>cbit)&1;
if (b) num ^= 1<<cbit;
if (!(x&(1<<cbit))) {
int ret = MOD;
ret = min(ret,test(num,trie[cur][b],cbit-1,0));
ret = min(ret,test(num^(1<<cbit),trie[cur][b^1],cbit-1,1));
return ret;
} else {
return test(num^(1<<cbit),trie[cur][b^1],cbit-1,0);
}
}
};
tri<10000000> t;
pi ans;
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> x;
FOR(i,1,n+1) {
cin >> cum[i];
cum[i] ^= cum[i-1];
}
FOR(i,1,n+1) {
t.ins(i-1);
int x = t.test(cum[i]);
ans = max(ans,{i-x,-(x+1)});
}
cout << -ans.s << " " << ans.f;
}
/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( )
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
428 KB |
Output is correct |
4 |
Correct |
3 ms |
560 KB |
Output is correct |
5 |
Correct |
7 ms |
1392 KB |
Output is correct |
6 |
Correct |
9 ms |
1552 KB |
Output is correct |
7 |
Correct |
9 ms |
1732 KB |
Output is correct |
8 |
Correct |
10 ms |
1936 KB |
Output is correct |
9 |
Correct |
43 ms |
11584 KB |
Output is correct |
10 |
Correct |
45 ms |
11820 KB |
Output is correct |
11 |
Correct |
46 ms |
11820 KB |
Output is correct |
12 |
Correct |
44 ms |
11820 KB |
Output is correct |
13 |
Correct |
44 ms |
11820 KB |
Output is correct |
14 |
Correct |
43 ms |
11820 KB |
Output is correct |
15 |
Correct |
43 ms |
11820 KB |
Output is correct |
16 |
Correct |
43 ms |
11820 KB |
Output is correct |
17 |
Correct |
122 ms |
23420 KB |
Output is correct |
18 |
Correct |
133 ms |
25324 KB |
Output is correct |
19 |
Correct |
126 ms |
27304 KB |
Output is correct |
20 |
Correct |
170 ms |
29392 KB |
Output is correct |