Submission #49867

#	Time	Username	Problem	Language	Result	Execution time	Memory
49867		mra2322001	XOR (IZhO12_xor)	C++14	0 / 100	4 ms	616 KiB

xor

#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(tu, ut) (((tu) >> (ut))&1)
#define F(tr) ((tr%2))

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

int n, a[N], f[N][30], d[N][30], x;
map <int, int> Map, pam;

int main(){
    ios_base::sync_with_stdio(0);
 
    cin >> n >> x;
    f1(i, n){
        cin >> a[i];
        f0(j, 30){
            f[i][j] = f[i - 1][j] + bit(a[i], j);
        }
    }

    for(int i = n; i >= 1; i--){
        int val = 0;
        for(int j = 30; j >= 0; j--){
            if(f[i][j]%2==1) val += (1 << j);
            if(Map[val]==0) Map[val] = i;
        }
        if(pam[val]==0) pam[val] = i;
    }
    if(x==0){
        cout << 1 << " " << n;
        return 0;
    }

    for(int i = 1; i <= n; i++){
        f0(j, 30){
            if(bit(a[i], j)){
                d[i][j] = i;
            }
            else{
                d[i][j] = d[i - 1][j];
            }
        }
    }
    int kbit = -1;
    for(int j = 30; j >= 0; j--) if(bit(x, j)){
        kbit = j;
        break;
    }
    int pos = -1, len = 0;
    f1(i, n){
        for(int j = 30; j > kbit; j--){
            /// khac bit tu bit thu j
            int dbit = f[n][j] - f[i - 1][j];
            if(dbit){
                int g = d[n][j];
                if(dbit%2==0) g = d[g - 1][j];
                /// i -> g
                if((g - i + 1) > len){
                    len = (g - i + 1);
                    pos = i;
                }
            }
        }
        for(int j = kbit; j > 0; j--){
            if(bit(x, j - 1)==0){
                /// giong nhau den bit thu j va khac nhau o bit j - 1
                x += (1 << (j - 1));
                int val = 0;
                for(int k = kbit; k >= j - 1; k--){
                    if(bit(x, k)==0){
                        if(F(f[i - 1][k])==1) val += (1 << k);
                    }
                    else{
                        if(F(f[i - 1][k])==0) val += (1 << k);
                    }
                }
                x -= (1 << (j - 1));
                int sop = Map[val];
                if(sop){
                    if((sop - i + 1) > len){
                        len = (sop - i + 1);
                        pos = i;
                    }
                }
            }
        }
    }
    /// now solve = x
    f1(i, n){
        int val = 0;
        for(int k = kbit; k >= 0; k--){
            if(bit(x, k)==0){
                if(F(f[i - 1][k])==1) val += (1 << k);
            }
            else{
                if(F(f[i - 1][k])==0) val += (1 << k);
            }
        }
        int sop = pam[val];
        if((sop - i + 1) > len){
            len = (sop - i + 1);
            pos = i;
        }
    }
    cout << pos << " " << len;
}

• Subtask 1: 0 / 100