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

• 問題: No.3598 Queen vs. King
• ユーザー: tkdgkb
• 提出日時: 2026-07-24 21:32:53
• 言語: C++23 (gcc 15.2.0 + boost 1.90.0)
• 結果: TLE
• 実行時間: -
• コード長: 4,281 bytes
• コンパイル時間: 2,285 ms
• コンパイル使用メモリ: 343,920 KB
• 実行使用メモリ: 145,280 KB
• 平均クエリ数: 1133.92
• 最終ジャッジ日時: 2026-07-24 21:33:00
• 合計ジャッジ時間: 6,700 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_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++)

const ll INF = 4e18;
const int MOD = 1e9+7;

ll modpow(ll a, ll b, ll m=MOD){
    ll r=1;
    while(b){
        if(b&1) r=r*a%m;
        a=a*a%m;
        b>>=1;
    }
    return r;
}

struct DSU{
    vi p,s;
    DSU(int n){p.resize(n);s.assign(n,1);iota(all(p),0);}
    int find(int x){return p[x]==x?x:p[x]=find(p[x]); }
    bool join(int a,int b){
        a=find(a); b=find(b);
        if(a==b) return 0;
        if(s[a]<s[b]) swap(a,b);
        p[b]=a; s[a]+=s[b];
        return 1;
    }
};

unsigned int dp[102][102][102][102];
unsigned int cur_t = 0;

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);
}

vector<pii> get_k(int kx, int ky, int qx, int qy, int h, int w) {
    vector<pii> r;
    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});
        }
    }
    return r;
}

vector<pii> get_q(int qx, int qy, int kx, int ky, int h, int w) {
    vector<pii> r;
    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];
        }
    }
    return r;
}

bool win(int qx, int qy, int kx, int ky, int rem, int h, int w, pii &bq) {
    if (rem <= 0) return 0;
    
    unsigned int &st = dp[qx][qy][kx][ky];
    if ((st >> 20) != cur_t) {
        st = (cur_t << 20);
    }
    
    unsigned int w_rem = (st >> 14) & 7;
    if (w_rem > 0 && w_rem <= (unsigned int)rem) {
        bq = {(st >> 7) & 127, st & 127};
        return 1;
    }
    if ((st >> 17) & (1u << (rem - 1))) {
        return 0;
    }

    auto qm = get_q(qx, qy, kx, ky, h, w);
    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);
    });

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

    for (auto [nx, ny] : qm) {
        auto km = get_k(kx, ky, nx, ny, h, w);
        if (km.empty()) {
            bq = {nx, ny};
            update_win(1, nx, ny);
            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);
            return 1;
        }
    }
    
    st |= (1u << (17 + rem - 1));
    return 0;
}

void solve() {
    cur_t++;
    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) {
            auto qm = get_q(qx, qy, kx, ky, h, w);
            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;
}