제출 #523764

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
523764		lukameladze	XOR (IZhO12_xor)	C++14	100 / 100	178 ms	90452 KiB

xor

# include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define int long long
using namespace std;
const int N = 3e5 + 5;
int n,x,a[N],pref,idx,sf[N],posri,le,mx,sz,idd,ty,cnt;
int trie[30*N][3],val[30*N][3];
void go(int lee , int rii ){
	sz = rii - lee + 1;
	if (sz >= mx) {
		le = lee;
		mx = sz; 
	}
}
void insert(int x, int id) {
	int cur = 0;
	for (int i = 30; i >= 0; i--) {
		if (x&(1<<i)) ty = 1; else ty = 0;
		if (!trie[cur][ty]) cnt++, trie[cur][ty] = cnt;
		//cout<<cur<<" "<<ty<<" "<<id<<endl;
		val[cur][ty] = max(val[cur][ty],id);
		cur = trie[cur][ty];
	}
}
void getans(int now, int x) {
	int cur = 0;
	for (int i = 30; i >= 0; i--) {
		if ((1<<i)&now) ty = 1; else ty = 0;
		//cout<<cur<<" "<<ty<<endl;
		if (x&(1<<i)) {
		    if (trie[cur][ty ^ 1])
			cur = trie[cur][ty ^ 1]; else break;
		} else {
			if (trie[cur][ty ^ 1])
			posri = max(mx,val[cur][ty ^ 1]) - 1;
			if (trie[cur][ty])
			cur = trie[cur][ty];
			else break;
		}
	}
}
main() {
    std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>x;
    for (int i = 1; i <= n; i++) {
        cin>>a[i];
    }
    for (int i = 30; i >= 0; i--) {
        if ((1LL<<i)&x) {
            idx = i;
            break;
        } 
        pref += (1<<i);
    }
    insert(0,n + 1);
    for(int i = n; i >= 1; i--) {
        sf[i] = sf[i + 1] ^ a[i];
        if ((pref&sf[i])) {
            le = i;
            mx = n - i + 1;
            if (!idd) idd = i;
            insert(sf[i],i);
            continue;
        }
        posri = 0;
        if (idd)
        posri = idd - 1;
        getans(sf[i],x - 1);
        if (posri - i + 1 >= mx) {
        	mx = posri - i + 1;
        	le = i;
		}
        insert(sf[i],i);
    }
    cout<<le<<" "<<mx<<endl;
}

컴파일 시 표준 에러 (stderr) 메시지

xor.cpp:44:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   44 | main() {
      | ^~~~

• Subtask 1: 100 / 100