Problem - E - Codeforces

Arseniy decided to make his friends Dabir and Egor happy. For this, he decided to give each of them an array of numbers of the same length. An array bb is called good if its elements can be rearranged so that for all i>1i \gt 1 the condition bi−bi−1=1b_i - b_{i - 1} = 1 holds.

Arseniy wants Dabir and Egor to be able to play with these arrays. For this, the following conditions must be satisfied:

  1. Each of the given arrays is good.
  2. If you write one array after the other (in other words, concatenate them), the resulting array is also good.

Arseniy already has an array aa of length nn. He plans to cut both arrays from aa, that is, to choose two non-overlapping subsegments of the same length. Help Arseniy determine the maximum possible length of the resulting arrays.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
int N;
  std::cin >> N;

  std::vector<int> cnt(N);
  for (int i = 0; i < N; i++) {
      int x;
      std::cin >> x;
      x--;
      cnt[x]++;
  }

  std::vector<std::vector<int>> segs;
  {
      std::vector<int> v;
      for (int i = 0; i <= N; i++) {
          if (i == N || cnt[i] == 0) {
              if (!v.empty()) {
                  segs.push_back(v);
                  v.clear();
              }
          } else {
              v.push_back(cnt[i]);
          }
      }
  }

  int ans = 0;
  if (segs.size() >= 2) {
      for (auto& v : segs) {
          ans = std::max(ans, int(v.size()));
      }
  }
  for (auto& seg : segs) {
      std::vector<int> v;
      int n = seg.size();
      ans = std::max(ans, n / 2);
      for (int i = 0; i <= n; i++) {
          if (i == n || seg[i] == 1) {
              if (!v.empty()) {
                  int l = v.front(), r = v.back();
                  ans = std::max(ans, std::min(r + 1, n - l));
                  v.clear();
              }
          } else {
              v.push_back(i);
          }
      }
  }
  std::cout << ans << "\n";