제출 #49871

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
49871		mra2322001	XOR (IZhO12_xor)	C++14	0 / 100	2088 ms	124868 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 <pair <int, int>, int> Map;
map <int, int> pam;

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

    cin >> n >> x;
    f1(i, n) cin >> a[i];
    f1(i, n){
        for(int j = 0; j < 30; j++){
            int bit = (a[i] >> j)&1;
            f[i][j] = f[i - 1][j] + bit;
        }
    }

    for(int i = n; i >= 1; i--){
        int val = 0;
        for(int j = 29; j >= 0; j--){
            if(f[i][j]%2==1) val += (1 << j);
            if(Map[make_pair(val, j)]==0) Map[make_pair(val, j)] = 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 = 29; j >= 0; j--) if(bit(x, j)){
        kbit = j;
        break;
    }
    int pos = -1, len = 0;
    f1(i, n){
        for(int j = 29; 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[make_pair(val, j - 1)];
                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;
    /*pos = 0, len = 0;
    f1(i, n){
        int val = 0;
        for(int j = i; j <= n; j++){
            val ^= a[j];
            if(val >= x){
                if((j - i + 1) > len){
                    len = (j - i + 1);
                    pos = i;
                }
            }
        }
    }
    cout << endl << pos << " " << len;
    int u = 0;
    f1(i, n) u ^= a[i];
    cout << endl << u;
    */
}

• Subtask 1: 0 / 100