# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
697948 |
2023-02-11T14:46:34 Z |
gagik_2007 |
XOR (IZhO12_xor) |
C++17 |
|
173 ms |
62284 KB |
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <chrono>
#include <ctime>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <limits>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <fstream>
#include <functional>
#include <random>
#include <cassert>
using namespace std;
typedef long long ll;
typedef long double ld;
#define ff first
#define ss second
const ll K = 2;
struct Vertex {
Vertex* to[K];
int cnt;
Vertex() {
for (ll i = 0; i < K; i++) {
to[i] = nullptr;
}
cnt = 1e8;
}
};
ll ttt;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ll N = 1000007;
const ll LG = 29;
ll n, m, k;
Vertex p;
ll a[N];
ll pf[N];
void add(int x, int vl) {
Vertex* v = &p;
(*v).cnt = min((*v).cnt, vl);
for (int i = LG; i >= 0; i--) {
//cout << i << endl;
int c = 0;
if (x & (1 << i)) {
c = 1;
}
if ((*v).to[c] == nullptr) {
//cout << "baba";
(*v).to[c] = new Vertex();
//cout << "baba";
}
v = (*v).to[c];
(*v).cnt = min((*v).cnt, vl);
}
}
int get_cnt(int vl) {
//cout << endl;
int cur = 0;
Vertex* v = &p;
int res = N;
for (int i = LG; i >= 0; i--) {
//cout << res << " " << v << endl;
if (vl & (1 << i)) {
if (cur + (1 << i) >= k && (*v).to[0] != nullptr) {
res = min(res, (*(*v).to[0]).cnt);
if ((*v).to[1] == nullptr) {
return res;
}
v = (*v).to[1];
}
else if ((*v).to[0] != nullptr) {
cur += (1 << i);
v = (*v).to[0];
}
else if (cur + (1 << i) >= k) {
v = (*v).to[1];
}
else {
return res;
}
}
else {
if (cur + (1 << i) >= k && (*v).to[1] != nullptr) {
//cout << "MT: 1" << endl;
res = min(res, (*(*v).to[1]).cnt);
if ((*v).to[0] == nullptr) {
return res;
}
v = (*v).to[0];
}
else if ((*v).to[1] != nullptr) {
//cout << "MT: 2" << endl;
cur += (1 << i);
v = (*v).to[1];
}
else if (cur + (1 << i) >= k) {
//cout << "MT: 3" << endl;
v = (*v).to[0];
}
else {
//cout << "MT: 4" << endl;
return res;
}
}
}
return res;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
if (i == 1)pf[i] = a[i];
else pf[i] = pf[i - 1] ^ a[i];
}
pair<int, int> ans = { -1,0 };
add(0, 0);
for (int i = 1; i <= n; i++) {
int ind = get_cnt(pf[i]);
//cout << ind << " ";
ans = max(ans, { i - ind,-ind });
//cout << ans << endl;
add(pf[i], i);
//cout << "AREC";
}
cout << -ans.ss + 1 << " " << ans.ff << endl;
return 0;
}
/// ---- - -------- ------ -------- -- - - -
/// Just a reminder. Ubuntu password is I O I
/// ---- - -------- ------ -------- -- - - -
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
596 KB |
Output is correct |
5 |
Correct |
6 ms |
2132 KB |
Output is correct |
6 |
Correct |
8 ms |
2380 KB |
Output is correct |
7 |
Correct |
7 ms |
2524 KB |
Output is correct |
8 |
Correct |
9 ms |
2644 KB |
Output is correct |
9 |
Correct |
76 ms |
29092 KB |
Output is correct |
10 |
Correct |
58 ms |
29236 KB |
Output is correct |
11 |
Correct |
56 ms |
29084 KB |
Output is correct |
12 |
Correct |
59 ms |
29140 KB |
Output is correct |
13 |
Correct |
57 ms |
29204 KB |
Output is correct |
14 |
Correct |
61 ms |
29160 KB |
Output is correct |
15 |
Correct |
59 ms |
29176 KB |
Output is correct |
16 |
Correct |
65 ms |
29140 KB |
Output is correct |
17 |
Correct |
156 ms |
62284 KB |
Output is correct |
18 |
Correct |
152 ms |
62256 KB |
Output is correct |
19 |
Correct |
173 ms |
62284 KB |
Output is correct |
20 |
Correct |
150 ms |
62276 KB |
Output is correct |