#1172997 (C++23) No.3598 Queen vs. King

• 問題: No.3598 Queen vs. King
• ユーザー: tkdgkb
• 提出日時: 2026-07-24 21:37:13
• 言語: C++23 (gcc 15.2.0 + boost 1.90.0)
• 結果: TLE
• 実行時間: -
• コード長: 4,594 bytes
• コンパイル時間: 2,273 ms
• コンパイル使用メモリ: 348,644 KB
• 実行使用メモリ: 11,904 KB
• 平均クエリ数: 1137.75
• 最終ジャッジ日時: 2026-07-24 21:37:30
• 合計ジャッジ時間: 6,628 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

ファイルパターン	結果
sample	AC * 2
other	AC * 5 TLE * 1 -- * 4

ソースコード

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using pii = pair<int,int>;
#define all(x) begin(x),end(x)
#define sz(x) (int)x.size()
#define rep(i,a,b) for(int i=a;i<b;i++)

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

unordered_map<long long, unsigned int, custom_hash> memo;

bool in(int x, int y, int h, int w) {
    return x >= 1 && x <= h && y >= 1 && y <= w;
}

bool atk(int qx, int qy, int x, int y) {
    return qx == x || qy == y || abs(qx - x) == abs(qy - y);
}

void get_k(int kx, int ky, int qx, int qy, int h, int w, vector<pii> &r) {
    r.clear();
    rep(dx, -1, 2) {
        rep(dy, -1, 2) {
            if (!dx && !dy) continue;
            int nx = kx + dx, ny = ky + dy;
            if (!in(nx, ny, h, w)) continue;
            if (nx == qx && ny == qy) continue;
            if (atk(qx, qy, nx, ny)) continue;
            r.push_back({nx, ny});
        }
    }
}

void get_q(int qx, int qy, int kx, int ky, int h, int w, vector<pii> &r) {
    r.clear();
    int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
    int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
    rep(i, 0, 8) {
        int nx = qx + dx[i], ny = qy + dy[i];
        while (in(nx, ny, h, w)) {
            if (nx == kx && ny == ky) break;
            r.push_back({nx, ny});
            nx += dx[i];
            ny += dy[i];
        }
    }
}

bool win(int qx, int qy, int kx, int ky, int rem, int h, int w, pii &bq) {
    if (rem <= 0) return 0;
    
    long long key = ((long long)qx << 21) | ((long long)qy << 14) | ((long long)kx << 7) | ky;
    auto it = memo.find(key);
    if (it != memo.end()) {
        unsigned int st = it->second;
        unsigned int w_rem = (st >> 14) & 7;
        if (w_rem > 0 && w_rem <= (unsigned int)rem) {
            bq = {(int)((st >> 7) & 127), (int)(st & 127)};
            return 1;
        }
        if ((st >> 17) & (1u << (rem - 1))) {
            return 0;
        }
    }

    vector<pii> qm;
    get_q(qx, qy, kx, ky, h, w, qm);
    auto dist = [&](pii p) {
        return max(abs(p.first - kx), abs(p.second - ky));
    };
    sort(all(qm), [&](pii a, pii b) {
        return dist(a) < dist(b);
    });

    unsigned int cur_st = 0;
    auto update_win = [&](int cw_rem, int bx, int by) {
        unsigned int cw = (cur_st >> 14) & 7;
        if (cw == 0 || cw > (unsigned int)cw_rem) {
            cur_st = (cur_st & ~((7u) << 14)) | ((unsigned int)cw_rem << 14);
            cur_st = (cur_st & ~((127u) << 7)) | ((unsigned int)bx << 7);
            cur_st = (cur_st & ~127u) | ((unsigned int)by);
        }
    };

    vector<pii> km;
    for (auto [nx, ny] : qm) {
        get_k(kx, ky, nx, ny, h, w, km);
        if (km.empty()) {
            bq = {nx, ny};
            update_win(1, nx, ny);
            memo[key] = cur_st;
            return 1;
        }
        if (rem == 1) continue;

        bool ok = 1;
        for (auto [nkx, nky] : km) {
            pii dmy;
            if (!win(nx, ny, nkx, nky, rem - 1, h, w, dmy)) {
                ok = 0;
                break;
            }
        }
        if (ok) {
            bq = {nx, ny};
            update_win(rem, nx, ny);
            memo[key] = cur_st;
            return 1;
        }
    }
    
    if (it != memo.end()) {
        cur_st = it->second;
    }
    cur_st |= (1u << (17 + rem - 1));
    memo[key] = cur_st;
    return 0;
}

void solve() {
    memo.clear();
    int h, w;
    if (!(cin >> h >> w)) exit(0);
    int qx = 1, qy = 1;
    int kx, ky;
    cin >> kx >> ky;
    if (kx == 0 && ky == 0) return;
    if (kx == -1 && ky == -1) exit(0);

    rep(turn, 1, 4) {
        pii bq;
        bool ok = win(qx, qy, kx, ky, 4 - turn, h, w, bq);
        if (!ok) {
            vector<pii> qm;
            get_q(qx, qy, kx, ky, h, w, qm);
            if (!qm.empty()) bq = qm[0];
        }
        qx = bq.first;
        qy = bq.second;
        cout << qx << " " << qy << "\n";
        cout.flush();

        cin >> kx >> ky;
        if (kx == 0 && ky == 0) return;
        if (kx == -1 && ky == -1) exit(0);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    if (cin >> t) {
        while (t--) solve();
    }
    return 0;
}