Submission #1124778

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124778		VinhLuu	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	85 / 85	391 ms	71248 KiB

necklace

#include <bits/stdc++.h>
//#define int long long
#define ll long long
#define all(lpv) lpv.begin(), lpv.end()
#define fi first
#define se second
#define pot(x, y) lower_bound(x.begin(), x.end(), y) - x.begin()
using namespace std;

typedef pair<int,int> pii;

const int N = 3e3 + 5;

int n, m, f[N][N], g[N][N];
vector<int> ask[N];
int open[N], le[5], ri[5];
string s, t;

//ull f[2][N], g[2][N], lt[N], base = 37;

int ans = 0;
pair<int,int> kq = {0, 0};
string a, b;

signed main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #define task "v"
  if(fopen(task ".inp","r")) {
    freopen(task ".inp","r",stdin);
    freopen(task ".out","w",stdout);
  }
  cin >> s >> t;
  n = s.size(), m = t.size();

  for(int msk = 0; msk < (1 << 2); msk ++) {
    bool f1 = ((msk >> 0) & 1);
    bool f2 = ((msk >> 1) & 1);
    a = s, b = t;
    if(f1) reverse(all(a));
    if(f2) reverse(all(b));

    for(int i = 1; i <= n; i ++) {
      for(int j = 1; j <= m; j ++) {
        if(a[i - 1] == b[j - 1]) f[i][j] = f[i - 1][j - 1] + 1;
        else f[i][j] = 0;
      }
    }

    for(int i = n; i >= 1; i --) {
      for(int j = m; j >= 1; j --) {
        if(a[i - 1] == b[j - 1]) g[i][j] = g[i + 1][j + 1] + 1;
        else g[i][j] = 0;
      }
    }
    for(int k = 2; k < n; k ++) {
      for(int i = 1; i <= m; i ++) ask[i].clear(), open[i] = 0;
      for(int i = 1; i <= m; i ++) {
        int pos = g[k][i];
        if(pos) {
          ask[i + pos - 1].push_back(i);
        }

        pos = f[k - 1][i];

        if(pos) {
          open[i - pos + 1] = max(open[i - pos + 1], i);
        }
      }
      int mx = 0;
      for(int i = 1; i <= m; i ++) {
        mx = max(mx, open[i]);
        for(auto pos : ask[i]) {
          int val = max(i, mx);
          if(i + 1 <= m) val = max(val, open[i + 1]);
          if(val - pos + 1 > ans) {
            int we = val - pos + 1;
            ans = val - pos + 1;
            ri[0] = k + (i - pos + 1) - 1, le[0] = ri[0] - we + 1;
            le[1] = pos, ri[1] = val;
            if(f1) le[0] = n - ri[0] + 1;
            if(f2) le[1] = m - ri[1] + 1;
            kq = {le[0] - 1, le[1] - 1};
          }
        }
      }
    }

    for(int i = 1; i <= m; i ++) {
      int pos = g[1][i];
      if(pos > ans) {
        ans = pos;
        le[0] = 1, ri[0] = le[0] + pos - 1;
        le[1] = i, ri[1] = le[1] + pos - 1;
        if(f1) le[0] = n - ri[0] + 1;
        if(f2) le[1] = m - ri[1] + 1;
        kq = {le[0] - 1, le[1] - 1};
      }
    }
    for(int i = 1; i <= m; i ++) {
      int pos = f[n][i];
      if(pos > ans) {
        ans = pos;
        le[0] = n - pos + 1, ri[0] = n;
        le[1] = i - pos + 1, ri[1] = i;
        if(f1) le[0] = n - ri[0] + 1;
        if(f2) le[1] = m - ri[1] + 1;
        kq = {le[0] - 1, le[1] - 1};
      }
    }
  }
  cout << ans << "\n";
  cout << kq.first << " " << kq.second;
}

Compilation message (stderr)

necklace.cpp: In function 'int main()':
necklace.cpp:29:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |     freopen(task ".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
necklace.cpp:30:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     freopen(task ".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 25 / 25
• Subtask 2: 20 / 20
• Subtask 3: 40 / 40