Submission #757225

#TimeUsernameProblemLanguageResultExecution timeMemory
757225pragmatistXOR (IZhO12_xor)C++17
0 / 100
5 ms8148 KiB
    /*
    #pragma comment(linker, "/stack:200000000")
    #pragma GCC optimize("O3")
    #pragma GCC target ("avx2")
    #pragma GCC optimize("Ofast")
    #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
    #pragma GCC optimize("unroll-loops")
    #pragma GCC target("avx2", "bmi", "bmi2", "lzcnt", "popcnt")
    */
     
    #include<bits/stdc++.h>
     
    #define sz(v) (int)v.size()
    #define ll long long
    #define pb push_back
    #define x first
    #define y second
    #define all(v) v.begin(), v.end()
    #define rall(v) v.rbegin(), v.rend()
    #define nl "\n"
     
    using namespace std;
    using pii = pair<int, int>;
     
    const int N = (int)25e4 + 7; // make sure this is right
    const int M = (int)2e6 + 7;
    const int inf = (int)1e9 + 7;
    const ll INF = (ll)3e18 + 7; 
    const ll MOD = (ll)998244353; // make sure this is right
     
    bool bit(int x, int i) {
    	return x >> i & 1;
    }
     
    int sum(int x, int y) {
    	x += y;
    	if(x >= MOD) x -= MOD;
    	return x;
    }
     
    pii dir[] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
     
    int n, k, p[N];
    int sz, t[M][2], mn[M];
     
    void add(int mask, int val) {
    	int v = 0;
    	for(int i = 29; i >= 0; --i) {
    		int x = bit(mask, i);
    		if(!t[v][x]) {
    			t[v][x] = ++sz;
    		}  
    		v = t[v][x];
    		mn[v] = min(mn[v], val);
    	}
    }
     
    int get(int mask) {
    	int v = 0, res = inf;
    	bool was = 1;
    	for(int i = 29; i >= 0; --i) {
    		int x = bit(k, i), y = bit(mask, i), c = 1 - y;
    		if(x == 1) {
    			if(!t[v][c]) {
    				was = 0;
    				break;
    			}
    	    	v = t[v][c];
    		} else {
    			res = min(res, mn[t[v][c]]);
    			if(!t[v][y]) {
    			    was = 0;
    				break;
    			}
    	    	v = t[v][y]; 			
    		}
    	}
    	return res;
    }
     
    void solve() {
    	cin >> n >> k;
    	fill(mn, mn + M, inf);
    	for(int i = 1; i <= n; ++i) {
    		cin >> p[i];
    		p[i] ^= p[i - 1];
    	}
    	int L = 0, R = -1;
    	add(0, 0);
    	for(int i = 1; i <= n; ++i) {
    		int j = get(p[i]);          
    		if(i - j > R - L + 1) {
    			L = j + 1, R = i;	
    		}
    		add(p[i], i);
    	}
    	cout << L << ' ' << R - L + 1;
    }
     
    signed main() {	
    	ios_base::sync_with_stdio(0);
    	cin.tie(0); 
    	//freopen("c.in", "r", stdin);
    	//freopen("c.out", "w", stdout);
    	int test = 1;
    	//cin >> test;
    	for(int i = 1; i <= test; ++i) {
    	 	//cout << "Case #" << i << ": ";
    		solve();
    	}
    	return 0;
    }

Compilation message (stderr)

xor.cpp: In function 'int get(int)':
xor.cpp:60:11: warning: variable 'was' set but not used [-Wunused-but-set-variable]
   60 |      bool was = 1;
      |           ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...