QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#707853#9537. Chinese Chessucup-team173WA 9ms4364kbC++206.2kb2024-11-03 17:50:342024-11-03 17:50:39

Judging History

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

  • [2024-11-03 17:50:39]
  • 评测
  • 测评结果:WA
  • 用时:9ms
  • 内存:4364kb
  • [2024-11-03 17:50:34]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define mpr make_pair
#define pb push_back
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});
                        }
                    }
                }
            }
        }
    }
    string ans = "JSCMXB";
    int n;
    cin >> n;
    vector<array<int, 3>> A;
    int flg = 1;
    vector<pair<int, int>> ve;
    ve.push_back({0, 4}), ve.push_back({5, 4}), ve.push_back({8, 4}), ve.push_back({2, 4});
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        if (i < ve.size() && ve[i] != make_pair(x, y)) flg = 0;
        for (int j = 0; j < 6; j++) {
            A.push_back({x, y, j});
        }
    }
    using T = unordered_map<int, vector<array<int, 3>>>;
    auto get = [&](int i, int j, const vector<array<int, 3>> &A) {
        T res;
        for (auto [x, y, ty] : A) {
            res[f[x][y][ty][i][j]].push_back({x, y, ty});
        }
        return res;
    };
    auto evalv = [&](const vector<array<int, 3>> &v) -> pair<int, int> {
        int sz = v.size();
        set<int> tys;
        for (auto [x, y, ty] : v) tys.insert(ty);
        return {(int)tys.size(), sz};
    };
    auto eval = [&](const T &mp) -> pair<int, int> {
        if (mp.size() == 0) return {1e9, 1e9};
        pair<int, int> mx = {-1, -1};
        for (auto [k, v] : mp) {
            mx = max(mx, evalv(v));
        }
        return mx;
    };
    int m = 0;
    int lim = 1000;
    vector<vector<array<int, 3>>> states = {A};
    vector<pair<pair<int,int>,vector<array<int, 3>>>>new_states;
    while (1) {
        m++;
        new_states.clear();
        for (auto AA : states) {
            T mp;
            for (int i = 0; i < 10; i++) {
                for (int j = 0; j < 9; j++) {
                    mp = get(i, j, AA);
                    vector<array<int, 3>> BB;
                    pair<int, int> val = {-1, -1};
                    for (auto [k, v] : mp) {
                        if (evalv(v) > val) {
                            val = evalv(v);
                            BB = v;
                        }
                    }
                    set<int> tys;
                    for (auto [x, y, ty] : BB) tys.insert(ty);
                    if (tys.size() == 1) {
                        // cout << "! " << ans[*tys.begin()] << endl;
                        goto fuck;
                    }
                    new_states.pb(mpr(val,BB));
                }
            }
        }
        sort(new_states.begin(),new_states.end());
        reverse(new_states.begin(),new_states.end());
        if(new_states.size()>lim){
            new_states.resize(lim);
        }
        states.clear();
        for(auto [a,b]:new_states){
            states.pb(b);
        }
    }
    fuck:;
    cout << m << endl;
    while (1) {
        T mp = get(0, 0, A);
        int qx = 0, qy = 0;
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < 9; j++) {
                auto now = get(i, j, A);
                if (eval(mp) > eval(now)) {
                    mp = now;
                    qx = i, qy = j;
                }
            }
        }
        cout << "? " << qx << ' ' << qy << endl;
        int res;
        cin >> res;
        if (flg) {
            for (auto [k, v] : mp) {
                cout << k << endl;
                for (auto [x, y, ty] : v) {
                    cout << "   " << x << ' ' << y << ' ' << ty << endl;
                }
            }
            cout << "res: " << res << endl;
            return;
        }
        assert(mp[res].size() > 0);
        // assert(A != mp[res]);
        A = mp[res];
        set<int> tys;
        for (auto [x, y, ty] : A) tys.insert(ty);
        if (tys.size() == 1) {
            cout << "! " << ans[*tys.begin()] << endl;
            break;
        }
    }
}
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: 4132kb

input:

1
9 0
8

output:

1
? 1 8
! S

result:

ok number is guessed.

Test #2:

score: 0
Accepted
time: 9ms
memory: 4328kb

input:

4
2 1
2 3
2 5
2 7
12
9

output:

2
? 7 0
? 0 0
! J

result:

ok number is guessed.

Test #3:

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

input:

1
2 4
-1
1

output:

2
? 0 0
? 0 2
! X

result:

ok number is guessed.

Test #4:

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

input:

1
5 0
6

output:

1
? 3 6
! S

result:

ok number is guessed.

Test #5:

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

input:

1
6 0
6

output:

1
? 0 2
! S

result:

ok number is guessed.

Test #6:

score: 0
Accepted
time: 4ms
memory: 4364kb

input:

2
7 7
1 0
5
14

output:

2
? 7 2
? 0 0
! J

result:

ok number is guessed.

Test #7:

score: 0
Accepted
time: 3ms
memory: 4068kb

input:

5
8 6
1 3
0 5
2 4
0 2
11
6

output:

2
? 9 0
? 0 0
! J

result:

ok number is guessed.

Test #8:

score: 0
Accepted
time: 6ms
memory: 4068kb

input:

6
0 7
1 6
2 8
0 5
7 6
8 2
11
-1

output:

2
? 9 7
? 0 0
! B

result:

ok number is guessed.

Test #9:

score: 0
Accepted
time: 5ms
memory: 4064kb

input:

7
6 5
3 0
3 2
4 1
4 0
2 4
5 2
9
3

output:

2
? 6 6
? 0 0
! J

result:

ok number is guessed.

Test #10:

score: 0
Accepted
time: 9ms
memory: 4128kb

input:

8
3 3
2 5
6 2
7 4
1 4
3 0
2 4
3 4
11
5

output:

2
? 9 1
? 0 0
! J

result:

ok number is guessed.

Test #11:

score: 0
Accepted
time: 9ms
memory: 4136kb

input:

9
2 7
2 4
2 5
2 2
2 1
2 0
2 6
2 3
2 8
8
9

output:

2
? 7 4
? 0 0
! J

result:

ok number is guessed.

Test #12:

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

input:

10
4 0
0 0
5 0
7 0
8 0
1 0
6 0
9 0
2 0
3 0
16
-1

output:

2
? 9 7
? 0 1
! B

result:

ok number is guessed.

Test #13:

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

input:

9
1 8
1 2
1 5
1 6
1 3
1 4
1 0
1 1
1 7
8
8

output:

2
? 6 4
? 0 0
! J

result:

ok number is guessed.

Test #14:

score: -100
Wrong Answer
time: 9ms
memory: 4068kb

input:

10
0 4
5 4
8 4
2 4
4 4
7 4
3 4
9 4
6 4
1 4
-1

output:

2
? 4 0
9
   9 4 0
7
   7 4 0
   1 4 0
1
   4 4 2
6
   2 4 0
   6 4 0
3
   5 4 3
   7 4 3
   3 4 3
   9 4 3
   1 4 3
5
   5 4 0
   3 4 0
-1
   0 4 5
   5 4 1
   5 4 4
   5 4 5
   8 4 5
   2 4 4
   2 4 5
   4 4 5
   7 4 1
   7 4 4
   7 4 5
   3 4 1
   3 4 4
   3 4 5
   9 4 1
   9 4 4
   9 4 5
   6 4 ...

result:

wrong answer Token "9" doesn't correspond to pattern "!|?"