TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

100.0% (1/1)

Description

給定一個長度為 $N$ 的環狀序列,每個元素都是非負整數。請將這個序列切成 $K$ 個連續段,使得每段的各個元素的 power AND 起來最大。一段的 power 是該段中所有元素的 OR

以下的程式是對於這個題目的一個假解。請寫一個程式,使得輸出的內容滿足 Input Format,且會讓以下程式碼獲得 Wrong Answer。你的程式不應該從標準輸入流中讀取任何東西。

#include <bits/stdc++.h>
using namespace std;

const int magic = 5;
const int maxn = 1e6 + 5;
int a[maxn], n, k;

bool check(int x) {
    int p = 0;
    for (int t = 0; t < magic; ++t) {
        int c = 0, s = 0, last = -1, i = p;
        for (int j = 0; j < n; ++j) {
            c |= a[i];
            if ((c & x) == x) {
                ++s;
                last = i + 1;
                c = 0;
                if (last >= n) last = 0;
            }
            if ((++i) >= n) i = 0;
        }
        if (s >= k) return true;
        p = last;
    }
    return false;
}

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
    int ans = 0;
    for (int b = 30; b >= 0; --b) {
        int x = ans + (1 << b);
        if (check(x)) ans = x;
    }
    printf("%d\n", ans);
    return 0;
}

Input Format

第一行有兩個整數 $N$ 及 $K$。
第二行有 $N$ 個整數 $A_1, A_2, A_3, \cdots, A_N$,依序代表環上的元素。

  • $1 \leq K \leq N \leq 5 \cdot 10^ 5$
  • $0 \leq A_i \leq 10^ 9$

Output Format

輸出一個數字,代表 $K$ 段的 power AND 起來的最大值。

Sample Input

# Sample Input 1
4 2
2 3 4 1

# Sample Input 2
6 3
2 2 2 4 4 4

# Sample Input 3
4 1
0 1 2 3

Sample Output

# Sample Output 1
3


# Sample Output 2
4


# Sample Output 3
3

Hints

Problem Source

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 262144 262144