Submission #895372

#	Time	Username	Problem	Language	Result	Execution time	Memory
895372		MilosMilutinovic	AAQQZ (JOI15_aaqqz)	C++14	100 / 100	102 ms	36072 KiB

aaqqz

#include <bits/stdc++.h>

using namespace std;

int BruteForce(vector<int> a) {
  int n = (int) a.size();
  int res = 0;
  int L, R;
  for (int l = 0; l < n; l++) {
    for (int r = l; r < n; r++) {
      vector<int> seq;
      for (int i = l; i <= r; i++) {
        seq.push_back(a[i]);
      }
      sort(seq.begin(), seq.end());
      vector<int> new_a = a;
      for (int j = l; j <= r; j++) {
        new_a[j] = seq[j - l];
      }
      vector<vector<bool>> f(n, vector<bool>(n));
      for (int i = n - 1; i >= 0; i--) {
        for (int j = i; j < n; j++) {
          if (i == j) {
            f[i][j] = true;
            continue;
          }
          if (new_a[i] == new_a[j]) {
            if (i + 1 == j) {
              f[i][j] = true;
            } else {
              f[i][j] = f[i + 1][j - 1];
            }
          }
        }
      }
      for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
          if (f[i][j]) {
            res = max(res, j - i + 1);
            if (res == j - i + 1) {
              L = l;
              R = r;
            }
          }
        }
      }
    }
  }
  cout << "-- " << L << " " << R << '\n';
  return res;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, c;
  cin >> n >> c;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    --a[i];
  }
  while (true) {
    int ans = 0;
    {
      vector<int> cnt(c);
      for (int i = 0; i < n; i++) {
        cnt[a[i]] += 1;
      }
      ans = max(ans, *max_element(cnt.begin(), cnt.end()));
    }
    for (int rot = 0; rot < 2; rot++) {
      vector<vector<int>> dp(n, vector<int>(n));
      for (int i = 0; i < n; i++) {
        for (int j = n - 1; j >= i; j--) {
          if (i == j) {
            dp[i][j] = 1 + (i > 0 && j + 1 < n ? dp[i - 1][j + 1] : 0);
          } else {
            if (a[i] != a[j]) {
              dp[i][j] = 0;
              continue;
            }
            dp[i][j] = 1 + (i > 0 && j + 1 < n ? dp[i - 1][j + 1] : 0);
          }
        }
      }
      auto Extend = [&](int L, int R, bool f) {
        ans = max(ans, R - L + 1);
        if (!f) {
          int ptr = R;
          vector<int> cnt(c);
          for (int i = L - 1; i >= 0; i--) {
            if (i < L - 1 && a[i] < a[i + 1]) {
              break;
            }
            bool ok = true;
            while (ptr + 1 < n && cnt[a[i]] == 0) {
              ptr += 1;
              if (a[ptr] < a[i]) {
                ok = false;
              }
              cnt[a[ptr]] += 1;
            }
            if (!cnt[a[i]] || !ok) {
              break;
            }
            cnt[a[i]] -= 1;
            for (int j = (i == L - 1 ? 0 : a[i + 1]); j < a[i]; j++) {
              if (cnt[j] > 0) {
                ok = false;
                break;
              }
            }
            if (!ok) {
              break;
            }
            int foo = 0;
            if (L - i == ptr - R && i > 0 && ptr + 1 < n) {
              foo = dp[i - 1][ptr + 1] * 2;
            }
            ans = max(ans, R - L + 1 + (L - i) * 2 + foo);
          }
        } else {
          int mn = c;
          for (int i = L + 1; i < n; i++) {
            if (a[i] < a[L]) {
              mn = a[i];
              break;
            }
          }
          if (mn == c) {
            return;
          }
          int ptr = R;
          vector<int> cnt(c);
          int cnt_mn = 0;
          for (int i = L; i >= 0; i--) {
            if (i < L && a[i] < a[i + 1]) {
              break;
            }
            bool ok = true;
            while (ptr + 1 < n && cnt[a[i]] == 0) {
              ptr += 1;
              if (a[ptr] < mn) {
                break;
              }
              if (a[ptr] != mn) {
                if (a[ptr] < a[i]) {
                  ok = false;
                  break;
                }
                cnt[a[ptr]] += 1;
              } else {
                cnt_mn += 1;
              }
            }
            if (!cnt[a[i]] || !ok) {
              break;
            }
            cnt[a[i]] -= 1;
            for (int j = (i == L ? 0 : a[i + 1]); j < a[i]; j++) {
              if (cnt[j] > 0) {
                ok = false;
                break;
              }
            }
            if (!ok) {
              break;
            }
            while (true) {
              int foo = 0;
              if (L - i + 1 == ptr - R - cnt_mn && i > 0 && ptr + 1 < n) {
                foo = dp[i - 1][ptr + 1] * 2;
              }
              ans = max(ans, (L - i + 1) * 2 + cnt_mn + foo);
              if (ptr + 1 < n && a[ptr + 1] == mn) {
                cnt_mn += 1;
                ptr += 1;
              } else {
                break;
              }
            }
          }

          vector<int> cntL(c), cntR(c);
          ptr = R;
          cnt_mn = 0;
          for (int i = L; i >= 0; i--) {
            if (i < L && a[i + 1] > a[i]) {
              break;
            }
            cntL[a[i]] += 1;
            bool ok = true;
            while (ptr + 1 < n) {
              if (a[ptr + 1] < mn) {
                break;
              } else if (a[ptr + 1] == mn) {
                cnt_mn += 1;
              } else {
                if (a[ptr + 1] < a[i]) {
                  break;
                }
                cntR[a[ptr + 1]] += 1;
              }
              ptr += 1;
            }
            if (cntL[a[i]] > cntR[a[i]] || !ok) {
              break;
            }
            if (!ok) {
              break;
            }
            for (int j = (i == L ? 0 : a[i + 1]); j < a[i]; j++) {
              while (ptr > R && cntR[j] > cntL[j]) {
                if (a[ptr] == mn) {
                  cnt_mn -= 1;
                  ptr -= 1;
                  continue;
                }
                cntR[a[ptr]] -= 1;
                if (cntL[a[ptr]] > cntR[a[ptr]]) {
                  ok = false;
                  break;
                }
                ptr -= 1;
              }
              if (cntR[j] > cntL[j]) {
                ok = false;
                break;
              }
            }
            if (!ok) {
              break;
            }
            ans = max(ans, (L - i + 1) * 2 + cnt_mn);
          }
        }
      };
      for (int i = 0; i < n; i++) {
        Extend(i - dp[i][i] + 1, i + dp[i][i] - 1, false);
        Extend(i, i, false);
        if (i + 1 < n && a[i] == a[i + 1]) {
          Extend(i - dp[i][i + 1] + 1, i + dp[i][i + 1], false);
        }
      }
      for (int i = 0; i < n; i++) {
        Extend(i, i, true);
      }
      for (int i = 0; i < n; i++) {
        a[i] = c - a[i] - 1;
      }
      reverse(a.begin(), a.end());
    }
    cout << ans << '\n';
   break;
  }
  return 0;
}

/*
10 6
5 5 4 0 1 1 0 5 3 4

7 4
2 3 2 2 3 3 1
*/

Compilation message (stderr)

aaqqz.cpp: In function 'int BruteForce(std::vector<int>)':
aaqqz.cpp:49:37: warning: 'R' may be used uninitialized in this function [-Wmaybe-uninitialized]
   49 |   cout << "-- " << L << " " << R << '\n';
      |                                     ^~~~
aaqqz.cpp:49:25: warning: 'L' may be used uninitialized in this function [-Wmaybe-uninitialized]
   49 |   cout << "-- " << L << " " << R << '\n';
      |                         ^~~

• Subtask 1: 10 / 10
• Subtask 2: 90 / 90