Submission #683731

#	Time	Username	Problem	Language	Result	Execution time	Memory
683731		nifeshe	XOR (IZhO12_xor)	C++17	100 / 100	1069 ms	48348 KiB

xor

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

//#pragma GCC target ("avx2")
//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("unroll-loops")
//#pragma comment (linker, "/STACK: 16777216")

#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((int)(x).size())
#define pb push_back
#define mp make_pair
#define int long long

using namespace std;
using namespace __gnu_pbds;

template <typename T> inline bool umax(T &a, const T &b) { if(a < b) { a = b; return 1; } return 0; }
template <typename T> inline bool umin(T &a, const T &b) { if(a > b) { a = b; return 1; } return 0; }
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template <typename T> using oset = tree<T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const ll mod = 998244353;
const ll base = 1e6 + 5;
const ll inf = 1e12;
const int MAX = 2e5 + 5;
const int LG = 31;

random_device rd;
mt19937 gen(rd());
uniform_int_distribution<ll> dis(1, inf);

void solve() {
    int n, x;
    cin >> n >> x;
    vector<int> a(n);
    for(auto &i : a) {
        cin >> i;
    }
    pair<int, int> ans = {0, 0};
    unordered_map<int, int> mn;
    mn[0] = 1;
    int xr = 0;
    for(int i = 0; i < n; i++) {
        xr ^= a[i];
        if(mn[xr ^ x]) umax(ans, {i - mn[xr ^ x] + 2, -mn[xr ^ x]});
        if(!mn[xr]) mn[xr] = i + 2;
    }
    for(int L = LG - 1; ~L; L--) {
        if(x >> L & 1) break;
        array<int, 2> pos;
        pos[0] = 1; pos[1] = 0;
        for(int i = 0; i < n; i++) {
            int b = a[i] >> L & 1;
            if(!pos[b]) pos[b] = i + 2;
            if(pos[b ^ 1]) {
                umax(ans, {i - pos[b ^ 1] + 2, -pos[b ^ 1]});
            }
        }
    }
    for(int L = LG - 1; L; L--) {
        if(x >> L - 1 & 1) continue;
        int nx = x;
        x |= (1 << L - 1);
        x >>= L - 1;
        unordered_map<int, int> mn;
        mn[0] = 1;
        int xr = 0;
        for(int i = 0; i < n; i++) {
            xr ^= (a[i] >> L - 1);
            if(mn[xr ^ x]) umax(ans, {i - mn[xr ^ x] + 2, -mn[xr ^ x]});
            if(!mn[xr]) mn[xr] = i + 2;
        }
        x = nx;
    }
    cout << -ans.s << " " << ans.f << '\n';
}

signed main() {
//    freopen("skyline.in", "r", stdin); freopen("skyline.out", "w", stdout);
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int ttt = 1;
//    cin >> ttt;
    while(ttt--) {
        solve();
    }
    return 0;
}

Compilation message (stderr)

xor.cpp: In function 'void solve()':
xor.cpp:68:19: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   68 |         if(x >> L - 1 & 1) continue;
      |                 ~~^~~
xor.cpp:70:22: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   70 |         x |= (1 << L - 1);
      |                    ~~^~~
xor.cpp:76:30: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   76 |             xr ^= (a[i] >> L - 1);
      |                            ~~^~~

• Subtask 1: 100 / 100