QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#200655#7051. Largest Common SubmatrixwjwHHHWA 1ms3520kbC++205.0kb2023-10-04 18:12:182023-10-04 18:12:19

Judging History

你现在查看的是最新测评结果

  • [2023-10-04 18:12:19]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3520kb
  • [2023-10-04 18:12:18]
  • 提交

answer

#include <bits/stdc++.h>
#define dug(x) cerr << "死了吧小丑" << x << endl
using namespace std;
using i64 = long long;
template <class T> void chmax(T &a, T b)
{
    a > b ? (a = a) : (a = b);
}
template <class T> void chmin(T &a, T b)
{
    a > b ? (a = b) : (a = a);
}
struct twostring_hash // 下标从0开始
{
    // using ui64 = unsigned long long;
    const int M = 1e9 + 7;
    i64 base1, base2;
    vector<i64> p1, p2;
    vector<vector<i64>> h;
    twostring_hash(vector<vector<int>> &a)
    {
        int n = a.size(), m = a[0].size();
        init(n, m);
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                h[i][j] = (h[i][j - 1] * base1 % M + a[i - 1][j - 1]) % M;
        for (int j = 1; j <= m; j++)
            for (int i = 1; i <= n; i++)
            {

                h[i][j] += h[i - 1][j] * base2 % M;
                h[i][j] %= M;
            }
    }
    void init(int l, int r, i64 b1 = 13331, i64 b2 = 131)
    {
        base1 = b1, base2 = b2;
        p1.resize(l + 1);
        p2.resize(r + 1);
        p1[0] = p2[0] = 1;
        for (int i = 1; i <= l; i++)
            p1[i] = p1[i - 1] * b1 % M;
        for (int i = 1; i <= r; i++)
            p2[i] = p2[i - 1] * b2 % M;
        h.resize(l + 1, vector<i64>(r + 1));
    }
    i64 get(pair<int, int> a, pair<int, int> b)
    {
        b.first++, b.second++;
        return (h[b.first][b.second] - h[a.first][b.second] * p2[b.first - a.first] % M -
                h[b.first][a.second] * p1[b.second - a.second] % M +
                (h[a.first][a.second] * p1[b.first - a.first] % M) * p2[b.second - a.second] + M) %
               M;
    }
};
struct tstring_hash // 下标从0开始
{
    // using ui64 = unsigned long long;
    const int M = 998244353;
    i64 base1, base2;
    vector<i64> p1, p2;
    vector<vector<i64>> h;
    tstring_hash(vector<vector<int>> &a)
    {
        int n = a.size(), m = a[0].size();
        init(n, m);
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                h[i][j] = (h[i][j - 1] * base1 % M + a[i - 1][j - 1]) % M;
        for (int j = 1; j <= m; j++)
            for (int i = 1; i <= n; i++)
            {

                h[i][j] += h[i - 1][j] * base2 % M;
                h[i][j] %= M;
            }
    }
    void init(int l, int r, i64 b1 = 13331, i64 b2 = 131)
    {
        base1 = b1, base2 = b2;
        p1.resize(l + 1);
        p2.resize(r + 1);
        p1[0] = p2[0] = 1;
        for (int i = 1; i <= l; i++)
            p1[i] = p1[i - 1] * b1 % M;
        for (int i = 1; i <= r; i++)
            p2[i] = p2[i - 1] * b2 % M;
        h.resize(l + 1, vector<i64>(r + 1));
    }
    i64 get(pair<int, int> a, pair<int, int> b)
    {
        b.first++, b.second++;
        return (h[b.first][b.second] - h[a.first][b.second] * p2[b.first - a.first] % M -
                h[b.first][a.second] * p1[b.second - a.second] % M +
                (h[a.first][a.second] * p1[b.first - a.first] % M) * p2[b.second - a.second] + M) %
               M;
    }
};
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << setprecision(15) << fixed;
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(n, vector<int>(m));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> a[i][j];
        }
    }
    vector<vector<int>> b(n, vector<int>(m));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> b[i][j];
        }
    }
    auto check=[&](pair<int,int>x,pair<int,int> y,pair<int,int>xx,pair<int,int>yy)
    {
        for(int i=x.first,ii=y.first;i<=xx.first;i++,ii++)
        {
            for(int j=x.second,jj=y.second;j<=xx.second;j++,jj++)
            {
                if(a[i][j]!=b[ii][jj])return false;
            }
        }
        return true;
    };
    map<int, pair<int, int>> mp;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            mp[b[i][j]] = pair(i, j);
        }
    }
    i64 ans = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            auto [rx, ry] = mp[a[i][j]];
            int l = 1, r = min(m - ry, m - j);
            while (l < r)
            {
                int mid = l + r + 1 >> 1;
                if (check(pair(i,j),pair(rx,ry),pair(i,j+mid-1),pair(rx,ry+mid-1)))
                    l = mid;
                else
                    r = mid - 1;
            }
            int len = l;
            l = 1, r = min(n - rx, n - i);
            while (l < r)
            {
                int mid = l + r + 1 >> 1;
                if (check(pair(i,j),pair(rx,ry),pair(i+mid-1,j+len-1),pair(rx+mid-1,ry+len-1)))
                    l = mid;
                else
                    r = mid - 1;
            }
            if(len*l!=1)cout<<a[i][j]<<endl;
            chmax(ans, 1ll * len * l);
        }
    }

    cout << ans << endl;
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3520kb

input:

3 4
5 6 7 8
1 2 3 4
9 10 11 12
5 6 8 7
1 2 4 3
12 11 10 9

output:

5
6
7
8
1
4

result:

wrong answer 1st numbers differ - expected: '4', found: '5'