QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #200647 | #7051. Largest Common Submatrix | wjwHHH | Compile Error | / | / | C++14 | 5.1kb | 2023-10-04 18:10:55 | 2023-10-04 18:10:55 |
Judging History
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 = 1331, 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] * p2[b.first - a.first] % M) * p1[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 = 1331, 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] * p2[b.first - a.first] % M) * p1[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];
}
}
twostring_hash ha(a), hb(b);
tstring_hash hha(a), hhb(b);
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 (ha.get(pair(i, j), pair(i, j + mid - 1)) == hb.get(pair(rx, ry), pair(rx, ry + mid - 1)) &&
hha.get(pair(i, j), pair(i, j + mid - 1)) == hhb.get(pair(rx, ry), 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 (ha.get(pair{i, j}, pair(i + mid - 1, j + len - 1)) ==
hb.get(pair(rx, ry), pair(rx + mid - 1, ry + len - 1)) &&
hha.get(pair{i, j}, pair(i + mid - 1, j + len - 1)) ==
hhb.get(pair(rx, ry), 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;
}
詳細信息
answer.code: In function ‘int main()’:
answer.code:129:31: error: missing template arguments before ‘(’ token
129 | mp[b[i][j]] = pair(i, j);
| ^
answer.code:137:18: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’
137 | auto [rx, ry] = mp[a[i][j]];
| ^
answer.code:142:32: error: missing template arguments before ‘(’ token
142 | if (ha.get(pair(i, j), pair(i, j + mid - 1)) == hb.get(pair(rx, ry), pair(rx, ry + mid - 1)) &&
| ^
answer.code:142:44: error: missing template arguments before ‘(’ token
142 | if (ha.get(pair(i, j), pair(i, j + mid - 1)) == hb.get(pair(rx, ry), pair(rx, ry + mid - 1)) &&
| ^
answer.code:142:76: error: missing template arguments before ‘(’ token
142 | if (ha.get(pair(i, j), pair(i, j + mid - 1)) == hb.get(pair(rx, ry), pair(rx, ry + mid - 1)) &&
| ^
answer.code:142:90: error: missing template arguments before ‘(’ token
142 | if (ha.get(pair(i, j), pair(i, j + mid - 1)) == hb.get(pair(rx, ry), pair(rx, ry + mid - 1)) &&
| ^
answer.code:143:33: error: missing template arguments before ‘(’ token
143 | hha.get(pair(i, j), pair(i, j + mid - 1)) == hhb.get(pair(rx, ry), pair(rx, ry + mid - 1)))
| ^
answer.code:143:45: error: missing template arguments before ‘(’ token
143 | hha.get(pair(i, j), pair(i, j + mid - 1)) == hhb.get(pair(rx, ry), pair(rx, ry + mid - 1)))
| ^
answer.code:143:78: error: missing template arguments before ‘(’ token
143 | hha.get(pair(i, j), pair(i, j + mid - 1)) == hhb.get(pair(rx, ry), pair(rx, ry + mid - 1)))
| ^
answer.code:143:92: error: missing template arguments before ‘(’ token
143 | hha.get(pair(i, j), pair(i, j + mid - 1)) == hhb.get(pair(rx, ry), pair(rx, ry + mid - 1)))
| ^
answer.code:153:32: error: missing template arguments before ‘{’ token
153 | if (ha.get(pair{i, j}, pair(i + mid - 1, j + len - 1)) ==
| ^
answer.code:153:44: error: missing template arguments before ‘(’ token
153 | if (ha.get(pair{i, j}, pair(i + mid - 1, j + len - 1)) ==
| ^
answer.code:154:36: error: missing template arguments before ‘(’ token
154 | hb.get(pair(rx, ry), pair(rx + mid - 1, ry + len - 1)) &&
| ^
answer.code:154:50: error: missing template arguments before ‘(’ token
154 | hb.get(pair(rx, ry), pair(rx + mid - 1, ry + len - 1)) &&
| ^
answer.code:155:33: error: missing template arguments before ‘{’ token
155 | hha.get(pair{i, j}, pair(i + mid - 1, j + len - 1)) ==
| ^
answer.code:155:45: error: missing template arguments before ‘(’ token
155 | hha.get(pair{i, j}, pair(i + mid - 1, j + len - 1)) ==
| ^
answer.code:156:37: error: missing template arguments before ‘(’ token
156 | hhb.get(pair(rx, ry), pair(rx + mid - 1, ry + len - 1)))
| ^
answer.code:156:51: error: missing template arguments before ‘(’ token
156 | hhb.get(pair(rx, ry), pair(rx + mid - 1, ry + len - 1)))
| ^