QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#712876#9537. Chinese Chessucup-team3519#RE 0ms0kbC++176.4kb2024-11-05 17:22:122024-11-05 17:22:12

Judging History

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

  • [2024-11-05 17:22:12]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-11-05 17:22:12]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
typedef long long LL;
#define fi first
#define se second
#define pb push_back
#define V vector
const int INF = 2e9 + 100;

char name[]{'J', 'S', 'C', 'M', 'X', 'B'};
V<pi> dir[]{
    {{1, 0}, {-1, 0}, {0, 1}, {0, -1}},
    {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}},
    {},//need
    {{2, 1}, {2, -1}, {-2, 1}, {-2, -1}, {1, 2}, {1, -2}, {-1, 2}, {-1, -2}},
    {{2, 2}, {2, -2}, {-2, 2}, {-2, -2}},
    {}
};

int query(int x, int y) {
    cout << "? " << x << " " << y << endl;
    int t; cin >> t;
    return t;
}

int dis[10][10][10][10][10];

bool ins(int x, int y) {
    return x >= 0 && x <= 9 && y >= 0 && y <= 8;
}

void ini_dis() {
    for(auto type : {0, 1, 3, 4}) {
        for(int i = 0; i <= 9; i++) {
            for(int j = 0; j <= 8; j++) {
                for(int x = 0; x <= 9; x++) {
                    for(int y = 0; y <= 8; y++) {
                        dis[type][i][j][x][y] = -1;
                    }
                }
                queue<pi> que;
                que.push({i, j});
                dis[type][i][j][i][j] = 0;
                while(que.size()) {
                    auto [p, q] = que.front();
                    que.pop();
                    for(auto [dx, dy] : dir[type]) {
                        int nx = p + dx, ny = q + dy;
                        if(ins(nx, ny) && dis[type][i][j][nx][ny] == -1) {
                            dis[type][i][j][nx][ny] = dis[type][i][j][p][q] + 1;
                            que.push({nx, ny});
                        }
                    }
                }
            }
        }
    }
    //deal2(car)
    for(int i = 0; i <= 9; i++) {
        for(int j = 0; j <= 8; j++) {
            for(int x = 0; x <= 9; x++) {
                for(int y = 0; y <= 8; y++) {
                    if(i == x && y == j) {
                        dis[2][i][j][x][y] = 0;
                    } else if(i == x || y == j) {
                        dis[2][i][j][x][y] = 1;
                    } else {
                        dis[2][i][j][x][y] = 2;
                    }
                }
            }
        }
    }
    //deal5(bing)
    for(int i = 0; i <= 9; i++) {
        for(int j = 0; j <= 8; j++) {
            for(int x = 0; x <= 9; x++) {
                for(int y = 0; y <= 8; y++) {
                    if(i > x || x <= 4 && j != y) {
                        dis[5][i][j][x][y] = -1;
                    } else {
                        dis[5][i][j][x][y] = abs(i - x) + abs(j - y);
                    }
                }
            }
        }
    }
}

bool ok(V<array<int, 3>> v) {
    bool ans = 1;
    for(int i = 1; i < v.size(); i++) {
        if(v[i][0] != v[i - 1][0]) {
            ans = 0;
            break;
        }
    }
    return ans;
}

V<array<int, 3>> upd(V<array<int, 3>> v, array<int, 3> info) {
    V<array<int, 3>> n_v;
    for(auto [type, x, y] : v) {
        if(dis[type][x][y][info[0]][info[1]] == info[2]) n_v.pb({type, x, y});
    }   
    return n_v;
}

pi tmp_ans;
bool dfs(int res, V<array<int, 3>> v, pi pre) {
    if(res == 0) {
        return ok(v);
    }
    if(res % 2 == 0) {
        for(int i = 0; i <= 9; i++) {
            for(int j = 0; j <= 8; j++) {
                if(dfs(res - 1, v, {i, j})) {
                    tmp_ans = pi{i, j};
                    return 1;
                }
            }
        }
        return 0;
    } else {
        bool ans = 1;
        for(int i = -1; i <= 17; i++) {
            V<array<int, 3>> n_v = upd(v, {pre.fi, pre.se, i});
            ans &= dfs(res - 1, n_v, {0, 0});
            if(!ans) return 0;
        }
        return 1;
    }
}

void solve1(V<array<int, 3>> v) {
    int t = query(tmp_ans.fi, tmp_ans.se);
    v = upd(v, {tmp_ans.fi, tmp_ans.se, t});
    assert(ok(v));
    cout << "! " << name[v[0][0]] << endl;
}

void solve2(V<array<int, 3>> v) {
    int t = query(tmp_ans.fi, tmp_ans.se);
    v = upd(v, {tmp_ans.fi, tmp_ans.se, t});

    assert(dfs(2, v, {0, 0}));
    t = query(tmp_ans.fi, tmp_ans.se);
    v = upd(v, {tmp_ans.fi, tmp_ans.se, t});
    assert(ok(v));
    cout << "! " << name[v[0][0]] << endl;
}

void solve3(V<array<int, 3>> v) {
    int t1 = query(0, 0);
    int t2 = query(9, 8);
    v = upd(v, {0, 0, t1});
    v = upd(v, {9, 8, t2});
    if(t1 == -1 && t2 == -1) {
        cout << "! " << 'X' << endl;
        assert(ok(v));
        return;
    }
    if(t1 == 0 && t2 == 17) {
        int t3 = query(0, 1);
        upd(v, {0, 1, t3});
        assert(ok(v));
        if(t3 == -1) {
            cout << "! " << 'B' << endl;
            return;
        } 
        if(t3 == 1) {
            cout << "! " << 'J' << endl;
            return;
        }
        assert(0);
    }
    if(t1 != -1 && t2 != -1) {
        assert(ok(v));
        int sum = t1 + t2;
        if(sum <= 4) {
            cout << "! " << 'C' << endl;
            return;
        }
        if(sum == 17) {
            cout << "! " << 'J' << endl;
            return;
        }
        cout << "! " << 'M' << endl;
        return;
    }
    if(t1 == -1) {
        int t3 = query(3, 2);
        v = upd(v, {3, 2, t3});
        assert(ok(v));

        int a = t2, b = t3;
        if(t2 == t3 + 12) {
            cout << "! B" << endl;
            return;
        } 
        if(a % 2 == b % 2) {
            cout << "! S" << endl;
            return;
        } else {
            cout << "! X" << endl;
            return;
        }
    }
    if(t2 == -1) {
        int t3 = query(1, 1);
        v = upd(v, {1, 1, t3});
        assert(ok(v));
        if(t3 == -1) cout << "! X" << endl;
        else cout << "! S" << endl;
        return;
    }
    assert(0);
}

void solve() {
    ini_dis();
    int n; cin >> n;
    V<pi> a(n + 1);
    for(int i = 1; i <= n; i++) cin >> a[i].fi >> a[i].se;
    V<array<int, 3>> v;
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j < 6; j++) {
            v.pb({j, a[i].fi, a[i].se});
        }
    }

    if(dfs(2, v, {0, 0})) {
        solve1(v);
    } else if(dfs(4, v, {0, 0})) {
        solve2(v);
    } else {
        solve3(v);
    }
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    // int t; cin >> t;
    // while(t--) 
        solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Runtime Error

input:

1
9 0

output:

? 1 8

result: