QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#54658#4195. Looking for WaldoAs3b_team_f_masr#WA 2ms3696kbC++4.6kb2022-10-10 02:11:272022-10-10 02:11:31

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-10 02:11:31]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3696kb
  • [2022-10-10 02:11:27]
  • 提交

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'