Submission #49875

#	Time	Username	Problem	Language	Result	Execution time	Memory
49875		mra2322001	XOR (IZhO12_xor)	C++14	0 / 100	2057 ms	133032 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);
 
    scanf("%d%d", &n, &x);
    f1(i, n) scanf("%d", &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;
        }
    }
    printf("%d %d", 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;
    */
}

Compilation message (stderr)

xor.cpp: In function 'int main()':
xor.cpp:18:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &x);
     ~~~~~^~~~~~~~~~~~~~~~
xor.cpp:19:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     f1(i, n) scanf("%d", &a[i]);
              ~~~~~^~~~~~~~~~~~~

• Subtask 1: 0 / 100