oj.uz

Submission #81826

# Submission time Handle Problem Language Result Execution time Memory
81826 2018-10-27T04:54:10 Z mra2322001 XOR (IZhO12_xor) C++14
100 / 100
 1089 ms 32840 KB 
#include <bits/stdc++.h>
#define f0(i, n) for(int i(0); i < (n); i++)
#define f1(i, n) for(int i(1); i <= n; i++)
#define bit(x, y) (((x) >> (y))&(1ll))

using namespace std;
typedef long long ll;
const int N = 250002;

int n, a[N], f[N], xo;
unordered_map <int, int> g;

void init(int b){
    g.clear();
    f0(i, n + 1){
        int x = f[i] >> b;
        g[x] = i;
    }
}

int main(){
    ios_base::sync_with_stdio(0);

    cin >> n >> xo;
    f1(i, n) cin >> a[i], f[i] = f[i - 1]^a[i], g[f[i]] = i;

    int res = 0, ans = 0;
    f0(i, n + 1){
        int cur = xo ^ f[i];
        int x = g[cur] - i;
        if(x > res) res = x, ans = i + 1;
    }
    for(int b = 29; b >= 0; b--){
        if(bit(xo, b)) continue;
        int now = (xo >> b);
        now ++;
        init(b);
        f0(i, n + 1){
            int x = f[i] >> b;
            int cur = now ^ x;
            int t = g[cur] - i;
            if(t > res) res = t, ans = i + 1;
            else if(t==res){
                if(i + 1 < ans) ans = i + 1;
            }
        }
    }
    cout << ans << " " << res;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 440 KB Output is correct
4 Correct 4 ms 616 KB Output is correct
5 Correct 13 ms 2136 KB Output is correct
6 Correct 21 ms 2376 KB Output is correct
7 Correct 16 ms 2376 KB Output is correct
8 Correct 17 ms 2568 KB Output is correct
9 Correct 198 ms 9144 KB Output is correct
10 Correct 190 ms 9272 KB Output is correct
11 Correct 187 ms 9272 KB Output is correct
12 Correct 146 ms 9284 KB Output is correct
13 Correct 140 ms 9284 KB Output is correct
14 Correct 143 ms 9284 KB Output is correct
15 Correct 261 ms 9284 KB Output is correct
16 Correct 178 ms 9284 KB Output is correct
17 Correct 1067 ms 27060 KB Output is correct
18 Correct 964 ms 28904 KB Output is correct
19 Correct 1089 ms 30848 KB Output is correct
20 Correct 776 ms 32840 KB Output is correct