QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#244908	#6305. Chinese Checker	hhoppitree^#	AC ✓	10ms	4112kb	C++14	6.4kb	2023-11-09 16:55:50	2023-11-09 16:55:51

Judging History

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

[2023-11-09 16:55:51]
评测

测评结果：AC
用时：10ms
内存：4112kb

查看

[2023-11-09 16:55:50]
提交

answer

#include <bits/stdc++.h>

using namespace std;

const int t1[30][30] = {{}, {0, 5}, {0, 5, 6}, {0, 5, 6, 7}, {0, 5, 6, 7, 8}, {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13}, {0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13}, {0, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13}, {0, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13}, {0, 5, 6, 7, 8, 9, 10, 11, 12, 13}, {0, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14}, {0, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}, {0, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16}, {0, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17}, {0, 10, 11, 12, 13}, {0, 11, 12, 13}, {0, 12, 13}, {0, 13}};
const int len[30] = {0, 1, 2, 3, 4, 13, 12, 11, 10, 9, 10, 11, 12, 13, 4, 3, 2, 1};
int t2[30][30], t[30], p1[30][30], p2[30][30];
pair<int, int> ys1[30][30], ys2[30][30];
int p[30][30], v[30][30];
vector<int> id1[30], id2[30], id3[30];

int calc(int x, int y)
{
    queue< pair<int, int> > Q;
    Q.push(make_pair(x, y));
    for (int i = 1; i <= 20; ++i) {
        id1[i].clear();
        id2[i].clear();
        id3[i].clear();
    }
    for (int i = 1; i <= 20; ++i) {
        for (int j = 1; j <= 20; ++j) {
            v[i][j] = 0;
            if (p[i][j] && (i != x || j != y)) {
                id1[i].push_back(j);
                id2[t1[i][j]].push_back(p1[i][j]);
                id3[t2[i][j]].push_back(p2[i][j]);
            }
        }
    }
    v[x][y] = 1;
    while (!Q.empty()) {
        int x = Q.front().first, y = Q.front().second;
        Q.pop();
        if (!id1[x].empty() && y < id1[x].back()) {
            int t = *lower_bound(id1[x].begin(), id1[x].end(), y);
            int z = t + t - y;
            if (z >= 1 && z <= len[x] && (upper_bound(id1[x].begin(), id1[x].end(), t) == id1[x].end() || *upper_bound(id1[x].begin(), id1[x].end(), t) > z)) {
                if (!v[x][z]) {
                    v[x][z] = 1;
                    Q.push(make_pair(x, z));
                }
            }
        }
        if (!id1[x].empty() && y > id1[x][0]) {
            int t = *--lower_bound(id1[x].begin(), id1[x].end(), y);
            int z = t + t - y;
            if (z >= 1 && z <= len[x] && (lower_bound(id1[x].begin(), id1[x].end(), t) == id1[x].begin() || *--lower_bound(id1[x].begin(), id1[x].end(), t) < z)) {
                if (!v[x][z]) {
                    v[x][z] = 1;
                    Q.push(make_pair(x, z));
                }
            }
        }
        if (!id2[t1[x][y]].empty() && p1[x][y] < id2[t1[x][y]].back()) {
            int t = *lower_bound(id2[t1[x][y]].begin(), id2[t1[x][y]].end(), p1[x][y]);
            int z = t + t - p1[x][y];
            if (z >= 1 && z <= len[t1[x][y]] && (upper_bound(id2[t1[x][y]].begin(), id2[t1[x][y]].end(), t) == id2[t1[x][y]].end() || *upper_bound(id2[t1[x][y]].begin(), id2[t1[x][y]].end(), t) > z)) {
                int ta = ys1[t1[x][y]][z].first, tb = ys1[t1[x][y]][z].second;
                if (!v[ta][tb]) {
                    v[ta][tb] = 1;
                    Q.push(make_pair(ta, tb));
                }
            }
        }
        if (!id2[t1[x][y]].empty() && p1[x][y] > id2[t1[x][y]][0]) {
            int t = *--lower_bound(id2[t1[x][y]].begin(), id2[t1[x][y]].end(), p1[x][y]);
            int z = t + t - p1[x][y];
            if (z >= 1 && z <= len[t1[x][y]] && (lower_bound(id2[t1[x][y]].begin(), id2[t1[x][y]].end(), t) == id2[t1[x][y]].begin() || *--lower_bound(id2[t1[x][y]].begin(), id2[t1[x][y]].end(), t) < z)) {
                int ta = ys1[t1[x][y]][z].first, tb = ys1[t1[x][y]][z].second;
                if (!v[ta][tb]) {
                    v[ta][tb] = 1;
                    Q.push(make_pair(ta, tb));
                }
            }
        }
        if (!id3[t2[x][y]].empty() && p2[x][y] < id3[t2[x][y]].back()) {
            int t = *lower_bound(id3[t2[x][y]].begin(), id3[t2[x][y]].end(), p2[x][y]);
            int z = t + t - p2[x][y];
            if (z >= 1 && z <= len[t2[x][y]] && (upper_bound(id3[t2[x][y]].begin(), id3[t2[x][y]].end(), t) == id3[t2[x][y]].end() || *upper_bound(id3[t2[x][y]].begin(), id3[t2[x][y]].end(), t) > z)) {
                int ta = ys2[t2[x][y]][z].first, tb = ys2[t2[x][y]][z].second;
                if (!v[ta][tb]) {
                    v[ta][tb] = 1;
                    Q.push(make_pair(ta, tb));
                }
            }
        }
        if (!id3[t2[x][y]].empty() && p2[x][y] > id3[t2[x][y]][0]) {
            int t = *--lower_bound(id3[t2[x][y]].begin(), id3[t2[x][y]].end(), p2[x][y]);
            int z = t + t - p2[x][y];
            if (z >= 1 && z <= len[t2[x][y]] && (lower_bound(id3[t2[x][y]].begin(), id3[t2[x][y]].end(), t) == id3[t2[x][y]].begin() || *--lower_bound(id3[t2[x][y]].begin(), id3[t2[x][y]].end(), t) < z)) {
                int ta = ys2[t2[x][y]][z].first, tb = ys2[t2[x][y]][z].second;
                if (!v[ta][tb]) {
                    v[ta][tb] = 1;
                    Q.push(make_pair(ta, tb));
                }
            }
        }
    }
    int res = -1;
    for (int i = 1; i <= 20; ++i) {
        for (int j = 1; j <= 20; ++j) {
            res += v[i][j];
        }
    }
    return res;
}

signed main()
{
    for (int i = 1; i <= 20; ++i) {
        for (int j = 1; j <= len[i]; ++j) {
            t2[i][j] = t1[i][len[i] - j + 1];
        }
    }
    for (int i = 1; i <= 20; ++i) {
        t[i] = 0;
    }
    for (int i = 1; i <= 20; ++i) {
        for (int j = 1; j <= len[i]; ++j) {
            p1[i][j] = ++t[t1[i][j]];
            ys1[t1[i][j]][p1[i][j]] = make_pair(i, j);
        }
    }
    for (int i = 1; i <= 20; ++i) {
        t[i] = 0;
    }
    for (int i = 1; i <= 20; ++i) {
        for (int j = 1; j <= len[i]; ++j) {
            p2[i][j] = ++t[t2[i][j]];
            ys2[t2[i][j]][p2[i][j]] = make_pair(i, j);
        }
    }
    int T;
    scanf("%d", &T);
    while (T--) {
        int n;
        scanf("%d", &n);
        for (int i = 1; i <= 20; ++i) {
            for (int j = 1; j <= 20; ++j) {
                p[i][j] = 0;
            }
        }
        for (int i = 1, x, y; i <= n; ++i) {
            scanf("%d%d", &x, &y);
            p[x][y] = 1;
        }
        int res = 0;
        for (int i = 1; i <= 20; ++i) {
            for (int j = 1; j <= 20; ++j) {
                if (p[i][j]) {
                    res += calc(i, j);
                }
            }
        }
        printf("%d\n", res);
    }
    return 0;
}

源文件, 语言: C++14

詳細信息

Test #1:

score: 100

Accepted

time: 0ms

memory: 3836kb

input:

output:

result:

ok 5 number(s): "0 1 2 6 13"

Test #2:

score: 0

Accepted

time: 8ms

memory: 4112kb

input:

output:

result:

ok 100 numbers

Test #3:

score: 0

Accepted

time: 7ms

memory: 4096kb

input:

output:

result:

ok 100 numbers

Test #4:

score: 0

Accepted

time: 7ms

memory: 4092kb

input:

output:

result:

ok 100 numbers

Test #5:

score: 0

Accepted

time: 7ms

memory: 3812kb

input:

output:

result:

ok 100 numbers

Test #6:

score: 0

Accepted

time: 7ms

memory: 3832kb

input:

output:

result:

ok 100 numbers

Test #7:

score: 0

Accepted

time: 8ms

memory: 3768kb

input:

output:

result:

ok 100 numbers

Test #8:

score: 0

Accepted

time: 9ms

memory: 3848kb

input:

output:

result:

ok 100 numbers

Test #9:

score: 0

Accepted

time: 9ms

memory: 3840kb

input:

output:

result:

ok 100 numbers

Test #10:

score: 0

Accepted

time: 10ms

memory: 3836kb

input:

output:

result:

ok 100 numbers