### SeniorLikeToCode's blog

By SeniorLikeToCode, history, 4 weeks ago,

Using segment tree to find the or of range [l, r] and checking if this is valid len we can choose. Also checking if this range [l, r] is equal to or of [0, n] , if not then we move to next len.

void solve() {
int n;
cin >> n;

vi a(n);
cin >> a;

vi seg(2 * n);
rep(i, 0, n) {
seg[i + n] = a[i];
}

rrep(i, n - 1, 1) {
seg[i] = seg[i << 1] | seg[i << 1 | 1];
}

auto query = [&](int l, int r) {
l += n; r += n + 1;
int res = 0;

while(l < r) {
if (l & 1) res |= seg[l++];
if (r & 1) res |= seg[--r];

l >>= 1;
r >>=1;
}

return res;
};

for(int i = 0; i < n; i++) {
int res = query(0, i);

if (res != query(0, n - 1)) continue;

bool fl = true;
for(int j = i; j < n; j++) {
if (res != query(j - i, j) ) {
fl = false;
break;
}
}

if (fl) return print(i + 1);
}

print(n);
}


It wasted my lot of time to prove in the contest why should I not submit this solution. Endup submitting it : (

• +2

 » 4 weeks ago, # |   +10 I hacked it with the obvious test case. You got lucky with weak system tests.
•  » » 4 weeks ago, # ^ |   0 Exactly, thanks
 » 4 weeks ago, # |   +9 Spoiler