oj.uz

Submission #716452

# Submission time Handle Problem Language Result Execution time Memory
716452 2023-03-30T06:22:11 Z vjudge1 XOR (IZhO12_xor) C++17
100 / 100
 1617 ms 99216 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 5e5 + 100;
const int mod = (int)1e9+7;
int n;
int a[maxn];
int x;
map<int, int> m[40], last;
int main() {
    ios_base::sync_with_stdio(false);
    cin >> n >> x;
    int pos = -1, len = -1;

    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] ^= a[i-1];
        if(a[i] >= x) {
            pos = 1;
            len = i;
        }
    }
    for(int i = 1; i <= n; i++) {
        int cur = 0;
        int val = 0;
        for(int j = 30; j >= 0; j--) {
            cur ^= (1<<j);
            cur ^= (a[i] & (1<<j));
            val |= a[i] & (1<<j);
            if(x&(1<<j)) {

            } else {
                if(m[j].count(cur)) {
                    if(i-m[j][cur] > len) {
                        pos = m[j][cur]+1;
                        len = i - m[j][cur];
                    }
                }
                cur ^= 1<<j;
            }
            if(m[j].count(val) == 0) m[j][val] = i;
        }
        if(last.count(a[i] ^ x) > 0) {
            if(i-last[a[i]^x] > len) {
                pos = last[a[i]^x] + 1;
                len = i-last[a[i]^x];
            }
        }
        if(last.count(a[i]) == 0) last[a[i]] = i;
    }
    cout << pos << " " << len << "\n";
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 3 ms 724 KB Output is correct
5 Correct 34 ms 3256 KB Output is correct
6 Correct 45 ms 3688 KB Output is correct
7 Correct 44 ms 3812 KB Output is correct
8 Correct 51 ms 4044 KB Output is correct
9 Correct 529 ms 45756 KB Output is correct
10 Correct 529 ms 46052 KB Output is correct
11 Correct 518 ms 45744 KB Output is correct
12 Correct 526 ms 45872 KB Output is correct
13 Correct 515 ms 46024 KB Output is correct
14 Correct 535 ms 46060 KB Output is correct
15 Correct 539 ms 45896 KB Output is correct
16 Correct 486 ms 45896 KB Output is correct
17 Correct 1491 ms 99076 KB Output is correct
18 Correct 1574 ms 99156 KB Output is correct
19 Correct 1617 ms 99216 KB Output is correct
20 Correct 1594 ms 99108 KB Output is correct