ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#213390 | #2068. 最长公共前缀 | ThySecret | 100 | 25048ms | 99412kb | C++11 | 3.2kb | 2024-11-11 21:19:36 | 2024-11-11 23:06:00 |
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
// #define x first
// #define y second
#define File(a) freopen(a".in", "r", stdin), freopen(a".out", "w", stdout)
inline void debug() { cerr << '\n'; }
template<typename Type, typename... Other>
inline void debug(const Type& x, const Other&... y) { cerr << x << ' '; debug(y...); }
#define DEBUG(a...) cerr << "[" << #a << "] = ", debug(a);
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
const int N = 2010;
const int INF = 0x3f3f3f3f;
const int base = 131;
template<typename Type>
inline void read(Type &res)
{
res = 0;
int ch = getchar(), flag = 0;
while (!isdigit(ch)) flag |= ch == '-', ch = getchar();
while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
res = flag ? -res : res;
}
template<typename Type, typename... Other>
inline void read(Type &res, Other&... y) { read(res), read(y...); }
int n, m, q;
char str[N][N];
ULL fc[N << 1], rhsh[N][N], dhsh[N][N], xhsh[N][N];
inline ULL gethash(int stx, int sty, int edx, int edy, int dir)
{
if (dir == 0)
return rhsh[edx][edy] - rhsh[stx][sty - 1] * fc[edy - sty + 1];
if (dir == 1)
return dhsh[edx][edy] - dhsh[stx - 1][sty] * fc[edx - stx + 1];
else return xhsh[edx][edy] - xhsh[stx - 1][sty - 1] * fc[edy - sty + 1];
}
inline int getborder(int x, int y, int dir)
{
if (dir == 0) return m - y + 1;
if (dir == 1) return n - x + 1;
if (dir == 2) return min(m - y + 1, n - x + 1);
}
inline bool check(int a, int b, int dir1, int x, int y, int dir2, int len)
{
ULL res1 = 0, res2 = 0;
if (dir1 == 0) res1 = gethash(a, b, a, b + len - 1, dir1);
if (dir1 == 1) res1 = gethash(a, b, a + len - 1, b, dir1);
if (dir1 == 2) res1 = gethash(a, b, a + len - 1, b + len - 1, dir1);
if (dir2 == 0) res2 = gethash(x, y, x, y + len - 1, dir2);
if (dir2 == 1) res2 = gethash(x, y, x + len - 1, y, dir2);
if (dir2 == 2) res2 = gethash(x, y, x + len - 1, y + len - 1, dir2);
return res1 == res2;
}
signed main()
{
for (int i = fc[0] = 1; i < N << 1; i ++)
fc[i] = fc[i - 1] * base;
read(n, m, q);
for (int i = 1; i <= n; i ++)
scanf("%s", str[i] + 1);
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
rhsh[i][j] = rhsh[i][j - 1] * base + str[i][j];
for (int j = 1; j <= m; j ++)
for (int i = 1; i <= n; i ++)
dhsh[i][j] = dhsh[i - 1][j] * base + str[i][j];
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
xhsh[i][j] = xhsh[i - 1][j - 1] * base + str[i][j];
int a, b, x, y;
char c[10], z[10];
while (q --)
{
scanf("%lld%lld%s%lld%lld%s", &a, &b, c, &x, &y, z);
int dir1 = *c == 'H' ? 0 : *c == 'V' ? 1 : 2, dir2 = *z == 'H' ? 0 : *z == 'V' ? 1 : 2;
int l = 1, r = min(getborder(a, b, dir1), getborder(x, y, dir2)), res = 0;
while (l <= r)
{
int mid = l + r >> 1;
if (check(a, b, dir1, x, y, dir2, mid)) res = mid, l = mid + 1;
else r = mid - 1;
}
cout << res << '\n';
}
return 0;
}
Details
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 11
Accepted
Test #1:
score: 11
Accepted
time: 49ms
memory: 50336kb
input:
1000 2000 10000 awanannwnnaaawwnwawanwnwaaaanwnaaananwawwwwnannannawwwawwaaaaannwnwnwnnaaawaawawannn...
output:
0 0 0 0 0 0 0 2 0 1 0 0 1 0 1 0 2 0 1 2 0 0 2 0 1 1 0 0 0 0 1 0 0 0 1 0 0 1 0 1 1 0 2 0 1 3 1 0 3 0 ...
result:
ok 10000 tokens
Test #2:
score: 0
Accepted
time: 50ms
memory: 76056kb
input:
2000 1000 10000 zzqzqqqqqzqqqqzqqqqzqzqzzzqqzqqqzzqzzqqqqqqqqqqqzzqzqqqzzqqzzqzqzzzqqzqqzzzzzzqzzzqq...
output:
0 3 3 1 0 2 2 2 1 0 1 0 0 0 1 0 2 0 6 1 0 1 1 0 2 1 1 1 2 4 0 1 3 2 1 0 1 2 0 0 0 1 1 0 1 1 0 4 0 3 ...
result:
ok 10000 tokens
Subtask #2:
score: 24
Accepted
Test #3:
score: 24
Accepted
time: 721ms
memory: 99408kb
input:
2000 2000 1000000 gggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggg...
output:
1146 541 203 322 618 166 345 138 520 206 1031 667 741 921 361 1110 1057 372 899 209 491 69 93 639 14...
result:
ok 1000000 tokens
Test #4:
score: 0
Accepted
time: 803ms
memory: 99412kb
input:
2000 2000 1000000 svsvsvvsvssssvsvvvvssvvvssvsvsvssssvvsvvvsvvsssvssssvssvvsvvvssssssvsvvvvsssvvvsss...
output:
2 0 2 1 2 0 0 1 3 1 0 0 0 1 0 1 0 1 0 6 1 2 2 1 3 5 0 0 1 1 0 0 2 1 1 3 1 0 0 2 1 0 0 0 0 0 1 0 5 0 ...
result:
ok 1000000 tokens
Test #5:
score: 0
Accepted
time: 891ms
memory: 99412kb
input:
2000 2000 1000000 qqqqqqqqqqqqqqqqcqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq...
output:
327 50 54 421 87 4 189 135 200 214 55 578 82 72 335 52 45 110 521 267 123 21 293 105 105 479 85 69 1...
result:
ok 1000000 tokens
Test #6:
score: 0
Accepted
time: 1111ms
memory: 99412kb
input:
2000 2000 1000000 ssssssssssssssssssssssssssgsssssssssssssssssssssssssssssssssssssssssssssssssssssss...
output:
187 336 26 367 487 65 159 30 12 275 628 200 252 742 362 7 316 232 26 82 607 158 56 444 155 262 1 106...
result:
ok 1000000 tokens
Test #7:
score: 0
Accepted
time: 1274ms
memory: 99408kb
input:
2000 2000 1000000 hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh...
output:
1281 105 890 1087 24 179 172 588 260 206 238 255 150 346 484 224 369 293 15 275 299 125 19 406 1146 ...
result:
ok 1000000 tokens
Test #8:
score: 0
Accepted
time: 737ms
memory: 99408kb
input:
2000 2000 1000000 cschgfyhvrlhmuchmcssqmxypkfkmkrfwpivfljvlascqlphvlbmjnztypqeoyevqecixdhricknhdrero...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 1000000 tokens
Test #9:
score: 0
Accepted
time: 782ms
memory: 99408kb
input:
2000 2000 1000000 cwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcw...
output:
0 0 0 0 118 0 0 0 0 0 0 0 0 0 0 0 0 0 178 0 0 0 297 0 0 0 0 0 0 63 0 0 0 115 0 0 0 699 955 0 325 0 0...
result:
ok 1000000 tokens
Subtask #3:
score: 22
Accepted
Test #10:
score: 22
Accepted
time: 1420ms
memory: 99412kb
input:
2000 2000 1000000 iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii...
output:
1182 916 1440 420 469 1353 818 143 458 743 25 1414 878 23 284 453 324 1652 10 556 276 448 1143 916 1...
result:
ok 1000000 tokens
Test #11:
score: 0
Accepted
time: 1112ms
memory: 99412kb
input:
2000 2000 1000000 ddddoddoodoodooddodododdodododdoooddodddddoodoodddddoodddodooddoddooooodddooodddoo...
output:
4 1 1 1 2 0 0 0 4 2 1 1 3 0 0 0 1 4 1 1 0 0 0 2 1 2 1 0 2 0 2 0 2 0 4 4 1 1 0 0 2 0 5 2 0 1 2 1 0 0 ...
result:
ok 1000000 tokens
Test #12:
score: 0
Accepted
time: 1715ms
memory: 99408kb
input:
2000 2000 1000000 dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd...
output:
180 74 19 380 126 169 75 17 53 352 123 150 258 103 65 17 87 109 11 164 407 143 241 407 214 256 84 22...
result:
ok 1000000 tokens
Test #13:
score: 0
Accepted
time: 1104ms
memory: 99408kb
input:
2000 2000 1000000 gggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggg...
output:
36 41 642 9 356 1100 529 595 2 299 253 559 761 245 494 259 43 234 430 885 449 225 404 211 213 32 38 ...
result:
ok 1000000 tokens
Test #14:
score: 0
Accepted
time: 1049ms
memory: 99408kb
input:
2000 2000 1000000 dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd...
output:
905 292 231 537 281 229 247 240 1460 110 261 530 378 569 206 163 1185 128 983 117 296 79 123 3 53 81...
result:
ok 1000000 tokens
Test #15:
score: 0
Accepted
time: 1227ms
memory: 99412kb
input:
2000 2000 1000000 nvmqmtwqkbpisvkrhgehqvohvizhldbhyiamavjuipxwxeqcqiqwcrjjlxeuvgzpgfwtcdgpymkptfemtv...
output:
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 1000000 tokens
Test #16:
score: 0
Accepted
time: 859ms
memory: 99408kb
input:
2000 2000 1000000 tctctctctctctctctctctctctctctctctctctctctctctctctctctctctctctctctctctctctctctctctc...
output:
0 0 0 0 0 0 0 0 0 0 1 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 344 0 0 0 0 0 0 0 0 0 0 0 1 0 0 546 0 0 0 1 1 ...
result:
ok 1000000 tokens
Subtask #4:
score: 43
Accepted
Test #17:
score: 43
Accepted
time: 1332ms
memory: 50336kb
input:
1000 2000 1000000 yzyzzyaazyyzzaaayzzayyyaaayyazayyzzyazzyazayzayzyzzayyzyzzayzazzyzzayzaazazaaayzyy...
output:
2 0 2 1 1 0 1 0 0 1 0 1 0 0 0 1 1 0 0 0 0 1 0 0 0 1 1 0 0 0 1 0 2 0 1 0 0 0 0 2 1 2 0 1 0 0 0 2 0 0 ...
result:
ok 1000000 tokens
Test #18:
score: 0
Accepted
time: 989ms
memory: 99408kb
input:
2000 2000 1000000 jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj...
output:
255 79 826 62 931 351 68 1020 265 697 2 1101 779 606 176 1568 696 615 106 596 185 311 65 397 816 25 ...
result:
ok 1000000 tokens
Test #19:
score: 0
Accepted
time: 1488ms
memory: 99412kb
input:
2000 2000 1000000 yyyvvyyyvyyyyvvvyyvyyyyvyyyyyyvvyvvyyyyyvvyyvvyvyvyvvvyyyvyvyvyyvyyyyvyyyvyyyvvyvy...
output:
3 0 0 0 0 1 0 0 0 0 1 2 0 2 1 0 0 0 4 2 0 0 3 1 1 2 3 1 0 1 1 0 0 3 0 0 0 2 0 0 1 0 1 0 0 3 2 0 0 1 ...
result:
ok 1000000 tokens
Test #20:
score: 0
Accepted
time: 1448ms
memory: 99412kb
input:
2000 2000 1000000 jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj...
output:
128 57 641 99 820 2 155 264 232 511 552 36 506 522 31 528 574 506 638 59 127 22 103 53 30 56 14 18 1...
result:
ok 1000000 tokens
Test #21:
score: 0
Accepted
time: 1559ms
memory: 99412kb
input:
2000 2000 1000000 ssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss...
output:
1 33 165 12 417 104 452 86 315 401 295 141 60 41 76 115 118 150 489 69 46 196 373 109 142 34 115 481...
result:
ok 1000000 tokens
Test #22:
score: 0
Accepted
time: 1073ms
memory: 99412kb
input:
2000 2000 1000000 iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii...
output:
371 247 218 9 492 569 21 454 121 168 207 251 176 236 333 23 138 1501 385 306 342 101 286 204 168 99 ...
result:
ok 1000000 tokens
Test #23:
score: 0
Accepted
time: 901ms
memory: 99412kb
input:
2000 2000 1000000 ccbxyakkmwxjxctespteblasatcayufpdpqvjjbmatywntdpcnhmwabgpmsyuxvqjtgxutglopldstpcmq...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 ...
result:
ok 1000000 tokens
Test #24:
score: 0
Accepted
time: 1354ms
memory: 99408kb
input:
2000 2000 1000000 mfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmf...
output:
0 0 0 0 2 0 0 1 0 1 0 0 0 0 0 0 2 1 0 361 0 0 0 1 0 0 0 0 1 1 0 1 0 0 1 0 0 0 0 0 323 0 0 0 1 0 0 1 ...
result:
ok 1000000 tokens