SeniorLikeToCode's blog

By SeniorLikeToCode, history, 2 months ago, In English

Question Solution

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 : (

Full text and comments »

  • Vote: I like it
  • +2
  • Vote: I do not like it