Submission #49452143

Source Code Expand

#include <bits/stdc++.h>

typedef long long valueType;
typedef std::vector<valueType> ValueVector;
typedef std::vector<ValueVector> ValueMatrix;
typedef std::vector<ValueMatrix> ValueCube;
typedef std::string string;
typedef std::vector<string> StringVector;
typedef std::vector<bool> bitset;
typedef std::vector<bitset> BitMatrix;
typedef std::pair<valueType, valueType> ValuePair;
typedef std::vector<ValuePair> PairVector;
typedef std::vector<PairVector> PairMatrix;
typedef std::tuple<valueType, valueType, valueType> ValueTuple;
typedef std::vector<ValueTuple> TupleVector;
typedef std::vector<TupleVector> TupleMatrix;
typedef std::set<valueType> ValueSet;
typedef std::vector<char> CharVector;
typedef std::vector<CharVector> CharMatrix;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    valueType H, W, K;

    std::cin >> H >> W >> K;

    CharMatrix S(H + 1, CharVector(W + 1, '#'));

    for (valueType i = 1; i <= H; ++i)
        for (valueType j = 1; j <= W; ++j)
            std::cin >> S[i][j];

    ValueMatrix X_Count(H + 1, ValueVector(W + 1, 0));
    ValueMatrix O_Count(H + 1, ValueVector(W + 1, 0));
    ValueMatrix Dot_Count(H + 1, ValueVector(W + 1, 0));

    for (valueType i = 1; i <= H; ++i) {
        for (valueType j = 1; j <= W; ++j) {
            X_Count[i][j] = X_Count[i][j - 1] + (S[i][j] == 'x');
            O_Count[i][j] = O_Count[i][j - 1] + (S[i][j] == 'o');
            Dot_Count[i][j] = Dot_Count[i][j - 1] + (S[i][j] == '.');
        }
    }

    for (valueType i = 1; i <= H; ++i) {
        for (valueType j = 1; j <= W; ++j) {
            X_Count[i][j] += X_Count[i - 1][j];
            O_Count[i][j] += O_Count[i - 1][j];
            Dot_Count[i][j] += Dot_Count[i - 1][j];
        }
    }

    auto Query_X = [&](valueType x1, valueType y1, valueType x2, valueType y2) {
        return X_Count[x2][y2] - X_Count[x1 - 1][y2] - X_Count[x2][y1 - 1] + X_Count[x1 - 1][y1 - 1];
    };

    auto Query_O = [&](valueType x1, valueType y1, valueType x2, valueType y2) {
        return O_Count[x2][y2] - O_Count[x1 - 1][y2] - O_Count[x2][y1 - 1] + O_Count[x1 - 1][y1 - 1];
    };

    auto Query_Dot = [&](valueType x1, valueType y1, valueType x2, valueType y2) {
        return Dot_Count[x2][y2] - Dot_Count[x1 - 1][y2] - Dot_Count[x2][y1 - 1] + Dot_Count[x1 - 1][y1 - 1];
    };

    valueType ans = std::numeric_limits<valueType>::max();

    for (valueType i = 1; i <= H; ++i) {
        for (valueType j = 1; j <= W - K + 1; ++j) {
            if (Query_X(i, j, i, j + K - 1) == 0)
                ans = std::min(ans, Query_Dot(i, j, i, j + K - 1));
        }
    }

    for (valueType i = 1; i <= H - K + 1; ++i) {
        for (valueType j = 1; j <= W; ++j) {
            if (Query_X(i, j, i + K - 1, j) == 0)
                ans = std::min(ans, Query_Dot(i, j, i + K - 1, j));
        }
    }

    if (ans == std::numeric_limits<valueType>::max())
        std::cout << -1 << std::endl;
    else
        std::cout << ans << std::endl;
}

Submission Info

Submission Time
Task D - Cheating Gomoku Narabe
User UserUnauthorized
Language C++ 20 (gcc 12.2)
Score 400
Code Size 3126 Byte
Status AC
Exec Time 40 ms
Memory 46928 KiB

Compile Error

Main.cpp: In function ‘int main()’:
Main.cpp:60:10: warning: variable ‘Query_O’ set but not used [-Wunused-but-set-variable]
   60 |     auto Query_O = [&](valueType x1, valueType y1, valueType x2, valueType y2) {
      |          ^~~~~~~

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 4
AC × 67
Set Name Test Cases
Sample example0.txt, example1.txt, example2.txt, example3.txt
All 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, 030.txt, 031.txt, 032.txt, 033.txt, 034.txt, 035.txt, 036.txt, 037.txt, 038.txt, 039.txt, 040.txt, 041.txt, 042.txt, 043.txt, 044.txt, 045.txt, 046.txt, 047.txt, 048.txt, 049.txt, 050.txt, 051.txt, 052.txt, 053.txt, 054.txt, 055.txt, 056.txt, 057.txt, 058.txt, 059.txt, 060.txt, 061.txt, 062.txt, example0.txt, example1.txt, example2.txt, example3.txt
Case Name Status Exec Time Memory
000.txt AC 1 ms 3584 KiB
001.txt AC 1 ms 3484 KiB
002.txt AC 1 ms 3432 KiB
003.txt AC 8 ms 14308 KiB
004.txt AC 8 ms 14296 KiB
005.txt AC 9 ms 14348 KiB
006.txt AC 8 ms 14436 KiB
007.txt AC 38 ms 46928 KiB
008.txt AC 39 ms 46864 KiB
009.txt AC 40 ms 46816 KiB
010.txt AC 40 ms 46856 KiB
011.txt AC 5 ms 8008 KiB
012.txt AC 5 ms 8784 KiB
013.txt AC 5 ms 8044 KiB
014.txt AC 7 ms 9844 KiB
015.txt AC 5 ms 8056 KiB
016.txt AC 5 ms 7996 KiB
017.txt AC 5 ms 8956 KiB
018.txt AC 6 ms 8004 KiB
019.txt AC 5 ms 7992 KiB
020.txt AC 5 ms 8324 KiB
021.txt AC 5 ms 8012 KiB
022.txt AC 5 ms 8060 KiB
023.txt AC 5 ms 8032 KiB
024.txt AC 5 ms 8060 KiB
025.txt AC 5 ms 8320 KiB
026.txt AC 5 ms 7996 KiB
027.txt AC 6 ms 8676 KiB
028.txt AC 6 ms 8008 KiB
029.txt AC 5 ms 8004 KiB
030.txt AC 6 ms 8912 KiB
031.txt AC 5 ms 7928 KiB
032.txt AC 5 ms 8004 KiB
033.txt AC 5 ms 8060 KiB
034.txt AC 6 ms 9376 KiB
035.txt AC 6 ms 8588 KiB
036.txt AC 5 ms 8056 KiB
037.txt AC 7 ms 10636 KiB
038.txt AC 5 ms 8012 KiB
039.txt AC 5 ms 7928 KiB
040.txt AC 6 ms 9112 KiB
041.txt AC 5 ms 8000 KiB
042.txt AC 5 ms 8056 KiB
043.txt AC 5 ms 8128 KiB
044.txt AC 5 ms 8052 KiB
045.txt AC 5 ms 8004 KiB
046.txt AC 5 ms 8052 KiB
047.txt AC 5 ms 8060 KiB
048.txt AC 5 ms 7992 KiB
049.txt AC 5 ms 7996 KiB
050.txt AC 6 ms 8264 KiB
051.txt AC 5 ms 8048 KiB
052.txt AC 5 ms 8008 KiB
053.txt AC 5 ms 8012 KiB
054.txt AC 5 ms 8048 KiB
055.txt AC 5 ms 8052 KiB
056.txt AC 5 ms 7924 KiB
057.txt AC 5 ms 8392 KiB
058.txt AC 5 ms 8060 KiB
059.txt AC 5 ms 8320 KiB
060.txt AC 5 ms 7928 KiB
061.txt AC 4 ms 8156 KiB
062.txt AC 5 ms 7928 KiB
example0.txt AC 1 ms 3312 KiB
example1.txt AC 1 ms 3316 KiB
example2.txt AC 1 ms 3412 KiB
example3.txt AC 1 ms 3408 KiB