QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#267867#5509. Kooky Tic-Tac-Toekilo_tobo_tarjen#AC ✓14ms3476kbC++208.5kb2023-11-27 20:00:272023-11-27 20:00:28

Judging History

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

  • [2023-11-27 20:00:28]
  • 评测
  • 测评结果：AC
  • 用时：14ms
  • 内存：3476kb
查看
  • [2023-11-27 20:00:27]
  • 提交

answer

#include <bits/stdc++.h>
// #include <bits/extc++.h>
// using namespace __gnu_cxx;
// using namespace __gnu_pbds;
using i64 = long long;
using namespace std;
const int N = 1e6 + 5;
// const int B = 500;
// const int M = 50005;
// const int base = 17131;
const int mod = 998244353;
// const int mod = 1e9 + 7;
// const double pi = acos(-1);

/*
1
3 3
xoo
oxx
xoo
*/
int n, k;
string s[10];
void solve()
{
    cin >> n >> k;
    int cnt0 = 0, cnt1 = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> s[i];
        cnt0 += count(s[i].begin(), s[i].end(), 'x');
        cnt1 += count(s[i].begin(), s[i].end(), 'o');
    }
    if (abs(cnt0 - cnt1) >= 2)
    {
        cout << "NIE\n";
        return;
    }
    map<pair<int, int>, int> c0, c1;
    int ok0 = 0, ok1 = 0;
    auto check1 = [&](int x, int y, char c) -> bool
    {
        bool res = true;
        for (int i = x; i < x + k; i++)
            if (s[i][y] != c)
                res = false;
        return res;
    };
    auto check2 = [&](int x, int y, char c) -> bool
    {
        bool res = true;
        for (int i = y; i < y + k; i++)
            if (s[x][i] != c)
                res = false;
        return res;
    };
    auto check3 = [&](int x, int y, char c) -> bool
    {
        bool res = true;
        for (int i = 0; i < k; i++)
            if (s[x + i][y + i] != c)
                res = false;
        return res;
    };
    auto check4 = [&](int x, int y, char c) -> bool
    {
        bool res = true;
        for (int i = 0; i < k; i++)
            if (s[x + i][y - i] != c)
                res = false;
        return res;
    };
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (i + k <= n)
            {
                if (check1(i, j, 'x'))
                {
                    ok0++;
                    for (int l = i; l < i + k; l++)
                        c0[{l, j}]++;
                }
                if (check1(i, j, 'o'))
                {
                    ok1++;
                    for (int l = i; l < i + k; l++)
                        c1[{l, j}]++;
                }
            }
            if (j + k <= n)
            {
                if (check2(i, j, 'x'))
                {
                    ok0++;
                    for (int l = j; l < j + k; l++)
                        c0[{i, l}]++;
                }
                if (check2(i, j, 'o'))
                {
                    ok1++;
                    for (int l = j; l < j + k; l++)
                        c1[{i, l}]++;
                }
            }
            if (i + k <= n && j + k <= n)
            {
                if (check3(i, j, 'x'))
                {
                    ok0++;
                    for (int l = 0; l < k; l++)
                        c0[{i + l, j + l}]++;
                }
                if (check3(i, j, 'o'))
                {
                    ok1++;
                    for (int l = 0; l < k; l++)
                        c1[{i + l, j + l}]++;
                }
            }
            if (i + k <= n && j >= k - 1)
            {
                if (check4(i, j, 'x'))
                {
                    ok0++;
                    for (int l = 0; l < k; l++)
                        c0[{i + l, j - l}]++;
                }
                if (check4(i, j, 'o'))
                {
                    ok1++;
                    for (int l = 0; l < k; l++)
                        c1[{i + l, j - l}]++;
                }
            }
        }
    }
    if (ok0 && ok1)
    {
        cout << "NIE\n";
        return;
    }
    if (!ok0 && !ok1 && cnt0 + cnt1 != n * n)
    {
        cout << "NIE\n";
        return;
    }
    vector<pair<int, int>> ans0, ans1;
    if (cnt0 == cnt1 + 1)
    {
        if (ok1)
        {
            cout << "NIE\n";
            return;
        }
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (s[i][j] == 'x')
                    ans0.push_back({i, j});
                else if (s[i][j] == 'o')
                    ans1.push_back({i, j});
        if (ok0)
        {
            bool flag = false;
            for (auto [t, x] : c0)
            {
                if (x == ok0)
                {
                    flag = true;
                    ans0.erase(find(ans0.begin(), ans0.end(), pair<int, int>{t.first, t.second}));
                    ans0.push_back({t.first, t.second});
                    break;
                }
            }
            if (!flag)
            {
                cout << "NIE\n";
                return;
            }
        }
        cout << "TAK\n";
        for (int i = 0, j = 0, k = 0; i < cnt0 + cnt1; i++)
        {
            if (i % 2 == 0)
                cout << ans0[j].first + 1 << ' ' << ans0[j].second + 1 << '\n', j++;
            else
                cout << ans1[k].first + 1 << ' ' << ans1[k].second + 1 << '\n', k++;
        }
        return;
    }
    if (cnt0 + 1 == cnt1)
    {
        if (ok0)
        {
            cout << "NIE\n";
            return;
        }
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (s[i][j] == 'x')
                    ans0.push_back({i, j});
                else if (s[i][j] == 'o')
                    ans1.push_back({i, j});
        if (ok1)
        {
            bool flag = false;
            for (auto [t, x] : c1)
            {
                if (x == ok1)
                {
                    flag = true;
                    ans1.erase(find(ans1.begin(), ans1.end(), pair<int, int>{t.first, t.second}));
                    ans1.push_back({t.first, t.second});
                    break;
                }
            }
            if (!flag)
            {
                cout << "NIE\n";
                return;
            }
        }
        cout << "TAK\n";
        for (int i = 0, j = 0, k = 0; i < cnt0 + cnt1; i++)
        {
            if (i % 2 == 0)
                cout << ans1[j].first + 1 << ' ' << ans1[j].second + 1 << '\n', j++;
            else
                cout << ans0[k].first + 1 << ' ' << ans0[k].second + 1 << '\n', k++;
        }
        return;
    }
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (s[i][j] == 'x')
                ans0.push_back({i, j});
            else if (s[i][j] == 'o')
                ans1.push_back({i, j});
    if (ok0)
    {
        bool flag = false;
        for (auto [t, x] : c0)
        {
            if (x == ok0)
            {
                flag = true;
                ans0.erase(find(ans0.begin(), ans0.end(), pair<int, int>{t.first, t.second}));
                ans0.push_back({t.first, t.second});
                break;
            }
        }
        if (!flag)
        {
            cout << "NIE\n";
            return;
        }
        cout << "TAK\n";
        for (int i = 0, j = 0, k = 0; i < cnt0 + cnt1; i++)
        {
            if (i % 2 == 0)
                cout << ans1[j].first + 1 << ' ' << ans1[j].second + 1 << '\n', j++;
            else
                cout << ans0[k].first + 1 << ' ' << ans0[k].second + 1 << '\n', k++;
        }
        return;
    }
    if (ok1)
    {
        bool flag = false;
        for (auto [t, x] : c1)
        {
            if (x == ok1)
            {
                flag = true;
                ans1.erase(find(ans1.begin(), ans1.end(), pair<int, int>{t.first, t.second}));
                ans1.push_back({t.first, t.second});
                break;
            }
        }
        if (!flag)
        {
            cout << "NIE\n";
            return;
        }
        cout << "TAK\n";
        for (int i = 0, j = 0, k = 0; i < cnt0 + cnt1; i++)
        {
            if (i % 2 == 0)
                cout << ans0[j].first + 1 << ' ' << ans0[j].second + 1 << '\n', j++;
            else
                cout << ans1[k].first + 1 << ' ' << ans1[k].second + 1 << '\n', k++;
        }
        return;
    }
    cout << "TAK\n";
    for (int i = 0, j = 0, k = 0; i < cnt0 + cnt1; i++)
    {
        if (i % 2 == 0)
            cout << ans0[j].first + 1 << ' ' << ans0[j].second + 1 << '\n', j++;
        else
            cout << ans1[k].first + 1 << ' ' << ans1[k].second + 1 << '\n', k++;
    }
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    cin >> t;
    cout << fixed << setprecision(12);
    while (t--)
        solve();
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3448kb

input:

7
3 3
x.o
xxx
o.o
4 3
xx.x
...o
..o.
.o..
3 3
xoo
oxx
xoo
3 2
xoo
oxx
xoo
3 3
xox
.o.
xox
3 2
xo.
..x
xo.
3 3
x..
.x.
..x

output:

TAK
1 1
1 3
2 2
3 1
2 3
3 3
2 1
TAK
1 1
3 3
1 2
4 2
1 4
2 4
TAK
1 2
1 1
1 3
2 2
2 1
2 3
3 2
3 1
3 3
NIE
NIE
NIE
NIE

result:

ok correct (7 test cases)

Test #2:

score: 0
Accepted
time: 8ms
memory: 3476kb

input:

10000
3 3
x.o
xxx
o.o
3 3
xoo
oxx
xoo
3 2
xoo
oxx
xoo
3 3
xox
.o.
xox
3 2
xo.
..x
xo.
3 2
oox
.xo
o.x
5 5
xxx..
xxo.x
xoo..
xxxox
.oooo
3 3
xxx
.o.
oo.
3 2
x.o
xo.
..o
3 2
..x
xxo
.o.
3 3
xxo
o..
oxo
3 2
oox
..x
...
3 3
xxo
...
.ox
3 3
.xo
...
oox
3 3
.x.
xo.
o.o
3 2
o..
xxo
.ox
3 2
x.x
xoo
x.o
3 2
...

output:

TAK
1 1
1 3
2 2
3 1
2 3
3 3
2 1
TAK
1 2
1 1
1 3
2 2
2 1
2 3
3 2
3 1
3 3
NIE
NIE
NIE
NIE
NIE
TAK
2 2
1 2
3 1
1 3
3 2
1 1
NIE
NIE
NIE
NIE
NIE
NIE
NIE
NIE
NIE
NIE
NIE
NIE
NIE
NIE
NIE
NIE
TAK
1 2
1 1
1 3
1 4
2 3
2 2
2 4
4 2
3 1
4 3
3 2
4 1
NIE
NIE
NIE
NIE
NIE
TAK
2 1
1 1
2 3
1 3
2 4
1 4
3 1
2 2
3 3
3 2
...

result:

ok correct (10000 test cases)

Test #3:

score: 0
Accepted
time: 14ms
memory: 3380kb

input:

10000
6 4
x.xx.o
xo.o.x
ooox.o
o..xo.
..xxxo
o.oxx.
6 5
oooxxx
oxoxxo
xoooxo
xoxxxx
xooxox
xoxxxx
6 3
o.x.x.
oo.o.x
xx.oo.
.x.xx.
ooxo..
.xxo..
6 6
xoo..o
o.xx.x
oooooo
xx.x..
o..xx.
...xxx
6 5
xooxoo
ooxxoo
xxooxx
oxooxx
oxoxxx
xxoxoo
6 5
xoxxxo
ooooxo
ooxoxx
oxxoox
xxxxox
ooooxo
6 5
o....o
.ox.oo
...

output:

TAK
1 6
1 1
2 2
1 3
2 4
1 4
3 1
2 1
3 2
2 6
3 3
4 4
3 6
5 3
4 1
5 4
4 5
5 5
5 6
6 4
6 1
6 5
6 3
3 4
NIE
TAK
1 3
1 1
1 5
2 1
2 6
2 2
3 1
2 4
3 2
3 4
4 2
3 5
4 4
5 1
4 5
5 2
6 2
5 4
6 3
6 4
5 3
NIE
TAK
1 1
1 2
1 4
1 3
2 3
1 5
2 4
1 6
3 1
2 1
3 2
2 2
3 5
2 5
3 6
2 6
4 2
3 3
4 5
3 4
4 6
4 1
5 2
4 3
5 4
...

result:

ok correct (10000 test cases)
English 繁體中文 简体中文

Server Time: 2024-12-04 22:05:43 | OpenSource Project