結果
| 問題 | No.3598 Queen vs. King |
| コンテスト | |
| ユーザー |
 tkdgkb
|
| 提出日時 | 2026-07-24 21:26:06 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.90.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,401 bytes |
| 記録 | |
| コンパイル時間 | 2,408 ms |
| コンパイル使用メモリ | 351,244 KB |
| 実行使用メモリ | 6,016 KB |
| 平均クエリ数 | 2.00 |
| 最終ジャッジ日時 | 2026-07-24 21:26:26 |
| 合計ジャッジ時間 | 9,082 ms |
|
ジャッジサーバーID （参考情報） |
judge2_0 / judge3_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | WA * 2 |
| other | WA * 4 RE * 6 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
using vi=vector<int>;
using vl=vector<ll>;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
template<class T>using pqg=priority_queue<T,vector<T>,greater<T>>;
#define all(x) begin(x),end(x)
#define rall(x) rbegin(x),rend(x)
#define sz(x) (int)x.size()
#define rep(i,a,b) for(int i=a;i<b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
const ll INF=4e18;
const int MOD=1e9+7;
const int MOD2=998244353;
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;}
};
struct BIT{
int n;vl b;
BIT(int n):n(n),b(n+1){}
void add(int i,ll v){for(;i<=n;i+=i&-i)b[i]+=v;}
ll sum(int i){ll r=0;for(;i;i-=i&-i)r+=b[i];return r;}
};
struct LazySeg{
int n;vl t,lz;
LazySeg(int n):n(n),t(4*n),lz(4*n){}
void push(int x,int l,int r){
if(!lz[x])return;
int m=(l+r)/2;
t[x*2]+=(m-l+1)*lz[x];
t[x*2+1]+=(r-m)*lz[x];
lz[x*2]+=lz[x];
lz[x*2+1]+=lz[x];
lz[x]=0;
}
void add(int x,int l,int r,int a,int b,ll v){
if(b<l||r<a)return;
if(a<=l&&r<=b){t[x]+=(r-l+1)*v;lz[x]+=v;return;}
push(x,l,r);
int m=(l+r)/2;
add(x*2,l,m,a,b,v);
add(x*2+1,m+1,r,a,b,v);
t[x]=t[x*2]+t[x*2+1];
}
};
struct Dinic{
struct E{int to,rev;ll cap;};
int n;vector<vector<E>>g;vi lv,it;
Dinic(int n):n(n),g(n),lv(n),it(n){}
void add(int a,int b,ll c){
g[a].push_back({b,(int)g[b].size(),c});
g[b].push_back({a,(int)g[a].size()-1,0});
}
bool bfs(int s,int t){
fill(all(lv),-1);
queue<int>q;q.push(s);lv[s]=0;
while(q.size()){
int x=q.front();q.pop();
for(auto&e:g[x])if(e.cap&&lv[e.to]<0)lv[e.to]=lv[x]+1,q.push(e.to);
}
return lv[t]>=0;
}
ll dfs(int x,int t,ll f){
if(x==t)return f;
for(int&i=it[x];i<sz(g[x]);i++){
auto&e=g[x][i];
if(e.cap&&lv[e.to]==lv[x]+1){
ll r=dfs(e.to,t,min(f,e.cap));
if(r){e.cap-=r;g[e.to][e.rev].cap+=r;return r;}
}
}
return 0;
}
ll flow(int s,int t){
ll r=0;
while(bfs(s,t)){
fill(all(it),0);
while(ll f=dfs(s,t,INF))r+=f;
}
return r;
}
};
vector<int> prefix(string s){
vector<int>p(sz(s));
rep(i,1,sz(s)){
int j=p[i-1];
while(j&&s[i]!=s[j])j=p[j-1];
if(s[i]==s[j])j++;
p[i]=j;
}
return p;
}
vector<int> zfunc(string s){
int n=sz(s),l=0,r=0;
vector<int>z(n);
rep(i,1,n){
if(i<=r)z[i]=min(r-i+1,z[i-l]);
while(i+z[i]<n&&s[z[i]]==s[i+z[i]])z[i]++;
if(i+z[i]-1>r)l=i,r=i+z[i]-1;
}
return z;
}
struct SAM{
struct Node{int nxt[26],link,len;Node(){memset(nxt,-1,sizeof(nxt));link=-1;len=0;}};
vector<Node>st;int last;
SAM(){st.push_back(Node());last=0;}
void add(char c){
int cur=sz(st);st.push_back(Node());st[cur].len=st[last].len+1;
int p=last;
while(p!=-1&&st[p].nxt[c-'a']==-1){st[p].nxt[c-'a']=cur;p=st[p].link;}
if(p==-1)st[cur].link=0;
else st[cur].link=st[p].nxt[c-'a'];
last=cur;
}
};
struct Point{
ld x,y;
Point(){}
Point(ld x,ld y):x(x),y(y){}
Point operator-(Point p){return {x-p.x,y-p.y};}
ld cross(Point p){return x*p.y-y*p.x;}
};
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;
for (int dx=-1; dx<=1; dx++) {
for (int dy=-1; dy<=1; dy++) {
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};
for(int i=0;i<8;i++){
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;
}
const int N = 105;
unsigned short fails[N][N][N][N];
int tc = 0;
bool win(int qx, int qy, int kx, int ky, int rem, int h, int w, pii &bq) {
if (rem <= 0) return 0;
unsigned short &f = fails[qx][qy][kx][ky];
if ((f >> 4) == tc) {
if ((f & 15) & (1 << rem)) 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);
});
for (auto [nx, ny] : qm) {
auto km = get_k(kx, ky, nx, ny, h, w);
if (km.empty()) {
bq = {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};
return 1;
}
}
if ((f >> 4) != tc) {
f = (tc << 4);
}
f |= (1 << rem);
return 0;
}
void solve() {
tc++;
int h, w;
if (!(cin >> h >> w)) return;
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; cin >> T;
//while(T--)
solve();
}