QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#707776#9537. Chinese Chessucup-team173RE 8ms4344kbC++205.2kb2024-11-03 17:29:282024-11-03 17:29:31

Judging History

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

  • [2024-11-03 17:29:31]
  • 评测
  • 测评结果:RE
  • 用时:8ms
  • 内存:4344kb
  • [2024-11-03 17:29:28]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

void solve() {
    auto valid = [&](int x, int y) {
        return 0 <= x && x < 10 && 0 <= y && y < 9;
    };
    auto getTo = [&](int x, int y, int ty) {
        vector<pair<int, int>> tmp;
        if(ty == 0) {
            for(int i = -1; i <= 1; i += 2) {
                tmp.push_back({x + i, y});
                tmp.push_back({x, y + i});
            }
        } else if(ty == 1) {
            for(int i = -1; i <= 1; i += 2) {
                for(int j = -1; j <= 1; j += 2) {
                    tmp.push_back({x + i, y + j});
                }
            }
        } else if(ty == 2) {
            for(int r = 0; r < 10; r++) if(r != x) tmp.push_back({r, y});
            for(int c = 0; c < 9; c++) if(c != y) tmp.push_back({x, c});
        } else if(ty == 3) {
            for(int i = -2; i <= 2; i += 4) {
                for(int j = -1; j <= 1; j += 2) {
                    tmp.push_back({x + i, y + j});
                    tmp.push_back({x + j, y + i});
                }
            }
        } else if(ty == 4) {
            for(int i = -2; i <= 2; i += 4) {
                for(int j = -2; j <= 2; j += 4) {
                    tmp.push_back({x + i, y + j});
                }
            }
        } else {
            tmp.push_back({x + 1, y});
            if(x > 4) {
                tmp.push_back({x, y + 1});
                tmp.push_back({x, y - 1});
            }
        }
        vector<pair<int, int>> res;
        for(auto [x, y] : tmp) if(valid(x, y)) res.push_back({x, y});
        return res;
    };
    vector f(10, vector(9, vector(6, vector(10, vector(9, -1)))));
    for(int i = 0; i < 10; i++) {
        for(int j = 0; j < 9; j++) {
            for(int ty = 0; ty < 6; ty++) {
                auto &g = f[i][j][ty];
                queue<pair<int, int>> q;
                q.push({i, j});
                g[i][j] = 0;
                while(q.size()) {
                    auto [x, y] = q.front(); q.pop();
                    for(auto [tx, ty] : getTo(x, y, ty)) {
                        if(g[tx][ty] == -1) {
                            g[tx][ty] = g[x][y] + 1;
                            q.push({tx, ty});
                        }
                    }
                }
            }
        }
    }
    int n;
    cin >> n;
    constexpr int N = 540;
    using B = bitset<N>;
    auto id = [&](int x, int y, int ty) {
        return (x * 9 + y) * 6 + ty;
    };
    auto rid = [&](int id) {
        return make_tuple(id / 6 / 9, id / 6 % 9, id % 6);
    };
    B A;
    for(int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        for(int j = 0; j < 6; j++) {
            A[id(x, y, j)] = 1;
        }
    }
    // A.flip();
    using T = unordered_map<int, B>;
    unordered_map<B, int> mp, g;
    unordered_map<B, T> G;
    unordered_map<B, pair<int, int>> best;
    auto print = [&](B A) {
        for(int id = A._Find_first(); id < N; id = A._Find_next(id)) {
            auto [x, y, t] = rid(id);
            cerr << "   " << x << ' ' << y << ' ' << t << endl;
        }
    };
    // print(A);
    auto get = [&](int i, int j, B &A) {
        T res;
        for(int id = A._Find_first(); id < N; id = A._Find_next(id)) {
            auto [x, y, t] = rid(id);
            res[f[x][y][t][i][j]][id] = 1;
        }
        return res;
    };
    auto getty = [&](B A) {
        vector<int> tys(6, 0);
        for(int i = A._Find_first(); i < N; i = A._Find_next(i)) {
            auto [x, y, ty] = rid(i);
            tys[ty]++;
        }
        if(accumulate(tys.begin(), tys.end(), 0) > 1) return -1;
        for(int i = 0; i < 6; i++) if(tys[i]) return i;
    };
    auto dfs1 = [&](auto self, B A, int dep, int mxdep) {
        if(dep > mxdep) return 10;
        if(g.count(A)) return g[A];
        if(getty(A) != -1) return g[A] = 0;
        // cerr << dep << '\n';
        g[A] = 10;
        for(int i = 0; i < 10; i++) {
            for(int j = 0; j < 9; j++) {
                auto nG = get(i, j, A);
                if(nG.size() == 1) continue;
                int mx = 0;
                for(auto [k, v] : nG) {
                    mx = max(mx, self(self, v, dep + 1, mxdep) + 1);
                }
                if(mx < g[A]) {
                    g[A] = mx;
                    best[A] = {i, j};
                    G[A] = nG;
                }
            }
        }
        return g[A];
    };
    dfs1(dfs1, A, 0, 3);
    cout << g[A] << endl;
    // cerr << g.size() << endl;
    // cerr << 1. * clock() / CLOCKS_PER_SEC << '\n';
    // return;
    auto dfs2 = [&](auto self, B A) {
        // print(A);
        // cerr << g[A] << '\n';
        if(getty(A) != -1) {
            cout << "! " << "JSCMXB"[getty(A)] << endl;
            return;
        }
        auto [x, y] = best[A];
        cout << "? " << x << ' ' << y << endl;
        int res;
        cin >> res;
        self(self, G[A][res]);
    };
    dfs2(dfs2, A);
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int t = 1;
    // cin >> t;
    while(t--) solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 8ms
memory: 4344kb

input:

1
9 0
8

output:

1
? 1 8
! S

result:

ok number is guessed.

Test #2:

score: -100
Runtime Error

input:

4
2 1
2 3
2 5
2 7

output:

10
? 0 0

result: