QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#54658 | #4195. Looking for Waldo | As3b_team_f_masr# | WA | 2ms | 3696kb | C++ | 4.6kb | 2022-10-10 02:11:27 | 2022-10-10 02:11:31 |
Judging History
answer
#include <bits/stdc++.h>
typedef long double ld;
typedef long long ll;
using namespace std;
int di[] = {1, 0, -1, -1, 0, 1, -1, 1};
int dj[] = {1, 1, 0, -1, -1, 0, 1, -1};
const ll oo = 1e18, MOD = 998244353;
const int N = 1e5 + 5, M = 350;
const ld PI = acos(-1.0), EPS = 1e-9;
//#define endl '\n'
int main() {
//ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//freopen("farm.in", "r", stdin);
//memset(dp, -1, sizeof dp);
int n, m;
cin >> n >> m;
int a[n + 5][m + 5][26];
for (int i = 0; i <= n; i++) for (int j = 0; j <= m; j++) for (int k = 0; k < 26; k++) a[i][j][k] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
char c;
cin >> c;
a[i][j][c - 'A']++;
}
}
for (int k = 0; k < 26; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) a[i][j][k] += a[i][j - 1][k];
}
for (int j = 1; j <= m; j++) {
for (int i = 1; i <= n; i++) a[i][j][k] += a[i - 1][j][k];
}
}
ll ans = oo;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
int l = j, r = m, mid, xl = i, xr = 0, yl = j, yr = 0;
while (l <= r) {
mid = (l + r) >> 1;
int num1 = a[n][mid][0] - a[n][yl - 1][0] - a[xl - 1][mid][0] + a[xl - 1][yl - 1][0];
int num2 = a[n][mid][3] - a[n][yl - 1][3] - a[xl - 1][mid][3] + a[xl - 1][yl - 1][3];
int num3 = a[n][mid][11] - a[n][yl - 1][11] - a[xl - 1][mid][11] + a[xl - 1][yl - 1][11];
int num4 = a[n][mid][14] - a[n][yl - 1][14] - a[xl - 1][mid][14] + a[xl - 1][yl - 1][14];
int num5 = a[n][mid][22] - a[n][yl - 1][22] - a[xl - 1][mid][22] + a[xl - 1][yl - 1][22];
if (!num1 || !num2 || !num3 || !num4 || !num5) l = mid + 1;
else yr = mid, r = mid - 1;
}
if (!yr) continue;
l = i, r = n;
while (l <= r) {
mid = (l + r) >> 1;
int num1 = a[mid][yr][0] - a[mid][yl - 1][0] - a[xl - 1][yr][0] + a[xl - 1][yl - 1][0];
int num2 = a[mid][yr][3] - a[mid][yl - 1][3] - a[xl - 1][yr][3] + a[xl - 1][yl - 1][3];
int num3 = a[mid][yr][11] - a[mid][yl - 1][11] - a[xl - 1][yr][11] + a[xl - 1][yl - 1][11];
int num4 = a[mid][yr][14] - a[mid][yl - 1][14] - a[xl - 1][yr][14] + a[xl - 1][yl - 1][14];
int num5 = a[mid][yr][22] - a[mid][yl - 1][22] - a[xl - 1][yr][22] + a[xl - 1][yl - 1][22];
if (!num1 || !num2 || !num3 || !num4 || !num5) l = mid + 1;
else xr = mid, r = mid - 1;
}
ans = min(ans, 1ll * (xr - xl + 1) * (yr - yl + 1));
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
int l = i, r = n, mid, xl = i, xr = 0, yl = j, yr = 0;
while (l <= r) {
mid = (l + r) >> 1;
int num1 = a[mid][m][0] - a[mid][yl - 1][0] - a[xl - 1][m][0] + a[xl - 1][yl - 1][0];
int num2 = a[mid][m][3] - a[mid][yl - 1][3] - a[xl - 1][m][3] + a[xl - 1][yl - 1][3];
int num3 = a[mid][m][11] - a[mid][yl - 1][11] - a[xl - 1][m][11] + a[xl - 1][yl - 1][11];
int num4 = a[mid][m][14] - a[mid][yl - 1][14] - a[xl - 1][m][14] + a[xl - 1][yl - 1][14];
int num5 = a[mid][m][22] - a[mid][yl - 1][22] - a[xl - 1][m][22] + a[xl - 1][yl - 1][22];
if (!num1 || !num2 || !num3 || !num4 || !num5) l = mid + 1;
else xr = mid, r = mid - 1;
}
if (!xr) continue;
l = j, r = m;
while (l <= r) {
mid = (l + r) >> 1;
int num1 = a[xr][mid][0] - a[xr][yl - 1][0] - a[xl - 1][mid][0] + a[xl - 1][yl - 1][0];
int num2 = a[xr][mid][3] - a[xr][yl - 1][3] - a[xl - 1][mid][3] + a[xl - 1][yl - 1][3];
int num3 = a[xr][mid][11] - a[xr][yl - 1][11] - a[xl - 1][mid][11] + a[xl - 1][yl - 1][11];
int num4 = a[xr][mid][14] - a[xr][yl - 1][14] - a[xl - 1][mid][14] + a[xl - 1][yl - 1][14];
int num5 = a[xr][mid][22] - a[xr][yl - 1][22] - a[xl - 1][mid][22] + a[xl - 1][yl - 1][22];
if (!num1 || !num2 || !num3 || !num4 || !num5) l = mid + 1;
else yr = mid, r = mid - 1;
}
ans = min(ans, 1ll * (xr - xl + 1) * (yr - yl + 1));
}
}
if (ans == oo) cout << "impossible";
else cout << ans;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3568kb
input:
5 5 ABCDE FGHIJ KLMNO PQRST VWXYZ
output:
25
result:
ok single line: '25'
Test #2:
score: 0
Accepted
time: 2ms
memory: 3696kb
input:
5 10 ABCDEABCDE FGHIJFGHIJ KLMNOKLMNO PQRSTPQRST VWXYZVWXYZ
output:
20
result:
ok single line: '20'
Test #3:
score: 0
Accepted
time: 2ms
memory: 3528kb
input:
5 10 WAALDLODOW AWWLAOODOW LOLADOWALO ADALLLWWOL WWOOAAAALO
output:
5
result:
ok single line: '5'
Test #4:
score: 0
Accepted
time: 2ms
memory: 3560kb
input:
2 3 WAL TER
output:
impossible
result:
ok single line: 'impossible'
Test #5:
score: 0
Accepted
time: 2ms
memory: 3540kb
input:
1 260 AWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWLDO
output:
260
result:
ok single line: '260'
Test #6:
score: 0
Accepted
time: 2ms
memory: 3584kb
input:
1 5 WALDO
output:
5
result:
ok single line: '5'
Test #7:
score: -100
Wrong Answer
time: 1ms
memory: 3516kb
input:
5 5 WXXAL XALDO XDOXX ALXXX DOXXX
output:
10
result:
wrong answer 1st lines differ - expected: '9', found: '10'