QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#497261 | #2567. Hidden Rook | zjjws | AC ✓ | 130ms | 3952kb | C++14 | 5.9kb | 2024-07-28 21:48:43 | 2024-07-28 21:48:44 |
Judging History
answer
#include <chrono>
#include <random>
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <vector>
#include <string>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#define LL long long
#define Conn(x,y) (x##y)
#define Tostring(x) (#x)
using namespace std;
bool ifnum(char x){return x>='0'&&x<='9';}
bool ifupchr(char x){return x>='A'&&x<='Z';}
bool iflochr(char x){return x>='a'&&x<='z';}
struct Rin
{
char c;
char gc()
{
return getchar();
}
Rin&operator >>(int &x)
{
bool tag=false;x=0;
for(c=gc();c>'9'||c<'0';c=gc())if(c=='-'){c=gc();tag=true;break;}
for(;c>='0'&&c<='9';c=gc())x=(x<<1)+(x<<3)+(c^'0');if(tag)x=-x;return *this;
}
Rin&operator >>(LL &x)
{
bool tag=false;x=0;
for(c=gc();c>'9'||c<'0';c=gc())if(c=='-'){c=gc();tag=true;break;}
for(;c>='0'&&c<='9';c=gc())x=(x<<1)+(x<<3)+(c^'0');if(tag)x=-x;return *this;
}
Rin&operator >>(char &x)
{
for(c=gc();!ifnum(c)&&!iflochr(c)&&!ifupchr(c);c=gc());
x=c;
return *this;
}
Rin&operator >>(string &x)
{
x.clear();
for(c=gc();!ifnum(c)&&!iflochr(c)&&!ifupchr(c);c=gc());
for(;ifnum(c)||iflochr(c)||ifupchr(c);c=gc())x.push_back(c);
return *this;
}
}rin;
#define rin(x) rin>>x
void jh(int &x,int &y){if(x^y)x^=y^=x^=y;return;}
void jh(LL &x,LL &y){if(x^y)x^=y^=x^=y;return;}
int min(int x,int y){return x<y?x:y;}
int max(int x,int y){return x>y?x:y;}
LL min(LL x,LL y){return x<y?x:y;}
LL max(LL x,LL y){return x>y?x:y;}
const int M=998244353;
#define lmod(i) if(i<0)i+=M
#define rmod(i) if(i>=M)i-=M
int ksm(int x,int y){int ans=1;for(;y;y>>=1){if(y&1)ans=1LL*ans*x%M;x=1LL*x*x%M;}return ans;}
void ad(int &x,int y){x+=y;rmod(x);return;}
void ac(int &x,int y){x-=y;lmod(x);return;}
int aad(int x,int y){x+=y;rmod(x);return x;}
int aac(int x,int y){x-=y;lmod(x);return x;}
#define yes {puts("YES");return;}
#define no {puts("NO");return;}
const int N=3e5+3;
int n,m;
int X,Y;
mt19937 engine(chrono::_V2::steady_clock::now().time_since_epoch().count());
inline int rand(int l,int r){return uniform_int_distribution<int>(l,r)(engine);}
int check(int x1,int y1,int x2,int y2)
{
printf("? %d %d %d %d\n",x1,y1,x2,y2);
int ans;cin>>ans;
// int ans=0;
// for(int i=x1;i<=x2;i++)for(int j=y1;j<=y2;j++)if(i==X||j==Y)ans++;
return ans;
}
void find(int x,int y)
{
printf("! %d %d\n",x,y);
// if(x!=X||y!=Y)
// {
// printf("n:%d m:%d X:%d Y:%d\n",n,m,X,Y);
// throw;
// }
return;
}
#define ady {if(s&2)ny2++;else ny1--;}
#define adx {if(s&1)nx2++;else nx1--;}
int cnt;
void work(int x1,int y1,int x2,int y2)
{
if(x1==x2&&y1==y2){find(x1,y1);return;}
if(x1==x2&&y1==y2-1)
{
if(x1!=1){if(check(x1-1,y1,x1,y1)==2)find(x1,y1);else find(x1,y2);}
else {if(check(x1,y1,x1+1,y1)==2)find(x1,y1);else find(x1,y2);}
return;
}
if(x1==x2-1&&y1==y2)
{
if(y1!=1){if(check(x1,y1-1,x1,y1)==2)find(x1,y1);else find(x2,y1);}
else {if(check(x1,y1,x1,y1+1)==2)find(x1,y1);else find(x2,y1);}
return;
}
if(x1==1&&y1==1&&x2==n&&y2==m)
{
int x=(x1+x2)>>1,y=(y1+y2)>>1;
if(x-x1==y-y1)
{
if(x!=2)
{
if(n>=m)y--;
else x--;
}
else
{
if(n>=m)x++;
else y++;
}
}
int v=check(x1,y1,x,y);
if(v==x-x1+1)work(x+1,y1,x2,y);
else if(v==y-y1+1)work(x1,y+1,x,y2);
else if(v==x-x1+y-y1+1)work(x1,y1,x,y);
else work(x+1,y+1,x2,y2);
return;
}
int s=((n-x2>x1-1)?1:0)+((m-y2>y1-1)?2:0);
int x=(x1+x2+(s&1))>>1,y=(y1+y2+((s&2)>0))>>1;
int nx1=min(x,(s&1)?x2:x1),nx2=max(x,(s&1)?x2:x1);
int ny1=min(y,(s&2)?y2:y1),ny2=max(y,(s&2)?y2:y1);
// printf("%d %d %d %d\n",nx1,ny1,nx2,ny2);
if(ny2==ny1)ady
if(nx2==nx1)adx
if(ny2-ny1==nx2-nx1)
{
// if(ny2-ny1==1)
// {
if((s&2)>0&&ny2<m)ny2++;
else if(!((s&2)>0)&&ny1>1)ny1--;
else if((s&1)>0&&nx2<n)nx2++;
else if(!((s&1)>0)&&nx1>1)nx1--;
// }
// else
// {
// if((s&2)>0)ny2--;
// else if()ny1++;
// }
}
// printf("work (%d,%d)-(%d,%d) check (%d,%d)-(%d,%d)\n",x1,y1,x2,y2,nx1,ny1,nx2,ny2);
int v=check(nx1,ny1,nx2,ny2);
// printf("s:%d v:%d\n",s,v);
if(v==nx2-nx1+1)
{
if(s&1)work(x1,max(ny1,y1),nx1-1,min(ny2,y2));
else work(nx2+1,max(ny1,y1),x2,min(ny2,y2));
}
else if(v==ny2-ny1+1)
{
if(s&2)work(max(nx1,x1),y1,min(nx2,x2),ny1-1);
else work(max(nx1,x1),ny2+1,min(nx2,x2),y2);
}
else if(v==0)
{
int xx1=(s&1)?x1:nx2+1,xx2=(s&1)?nx1-1:x2;
int yy1=(s&2)?y1:ny2+1,yy2=(s&2)?ny1-1:y2;
work(xx1,yy1,xx2,yy2);
}
else work(max(nx1,x1),max(ny1,y1),min(nx2,x2),min(ny2,y2));
}
void work()
{
cin>>n>>m;
// n=4;m=4;
// X=rand(1,n);Y=rand(1,m);
// X=2;Y=1;
// if((++cnt)==53)printf("%d%d fu2ck\n",n,m);
if(n==3&&m==3)
{
int s=check(1,1,3,2);
if(s==2)for(int i=1;i<=3;i++)if(check(i,2,i,3)==2){find(i,3);return;}
if(s==4)
{
s=check(1,1,2,3);
if(s==2){work(3,1,3,2);return;}
if(s==4)
{
if(check(1,2,2,2)==2){work(1,2,2,2);return;}
else {work(1,1,2,1);return;}
}
return;
}
throw;
}
work(1,1,n,m);
return;
}
int main()
{
int T;cin>>T;
for(;T-->0;)work();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3852kb
input:
2 6 6 2 4 2 7 5 3 2 2
output:
? 1 1 3 2 ? 2 2 3 4 ? 3 1 4 3 ! 2 3 ? 1 1 4 3 ? 3 2 4 4 ? 1 3 1 4 ! 1 4
result:
ok Good (2 test cases)
Test #2:
score: 0
Accepted
time: 0ms
memory: 3828kb
input:
3 15 15 14 4 2 4 3 15 8 5 3 1 15 15 7 8 2 0
output:
? 1 1 8 7 ? 5 4 8 8 ? 3 6 4 8 ? 2 7 3 9 ! 2 7 ? 1 1 2 8 ? 2 9 3 12 ? 1 8 2 10 ? 1 11 2 11 ! 2 12 ? 1 1 8 7 ? 5 7 8 11 ? 7 7 8 9 ? 6 6 7 8 ! 5 9
result:
ok Good (3 test cases)
Test #3:
score: 0
Accepted
time: 0ms
memory: 3772kb
input:
100 6 6 0 4 4 3 4 2 3 7 8 4 3 3 5 6 0 0 9 4 5 4 2 11 4 6 2 4 2 15 12 8 6 4 3 5 9 7 4 4 2 6 7 3 3 2 9 9 8 4 0 11 4 6 2 4 2 12 7 4 2 4 1 14 7 0 4 4 1 9 6 0 4 2 12 11 6 3 0 3 14 7 5 3 1 15 12 0 6 2 4 7 10 8 4 4 1 15 5 0 0 4 2 11 9 5 3 4 2 14 7 4 4 2 15 10 0 4 4 4 7 4 4 2 5 13 7 3 2 2 13 8 0 3 2 15 12 1...
output:
? 1 1 3 2 ? 4 2 5 4 ? 3 1 4 3 ! 4 3 ? 1 1 2 3 ? 2 2 3 4 ! 3 1 ? 1 1 3 4 ? 2 4 3 6 ? 3 5 4 7 ! 3 8 ? 1 1 2 3 ? 3 3 4 5 ! 5 6 ? 1 1 5 2 ? 6 2 7 4 ? 6 1 6 2 ! 6 2 ? 1 1 6 2 ? 7 2 9 3 ? 7 1 8 3 ? 7 1 7 2 ! 7 1 ? 1 1 8 6 ? 9 4 12 6 ? 9 5 10 7 ? 8 6 9 8 ! 9 5 ? 1 1 3 5 ? 2 3 3 5 ? 3 4 4 6 ? 2 4 3 4 ! 3 4 ...
result:
ok Good (100 test cases)
Test #4:
score: 0
Accepted
time: 2ms
memory: 3812kb
input:
50 9 8 0 2 2 4 11 0 2 4 2 9 11 6 6 2 1 13 8 4 0 4 1 4 15 8 0 4 2 8 9 4 2 0 11 12 5 3 2 2 11 14 0 0 4 1 14 14 0 4 4 3 8 3 5 0 2 6 7 6 0 1 4 12 6 2 4 1 6 4 4 2 9 15 0 2 0 2 12 7 9 4 3 1 13 14 6 8 4 0 12 11 0 6 2 2 12 13 6 6 3 2 8 5 6 3 2 8 10 5 4 2 1 13 3 7 0 2 8 10 0 3 4 15 15 7 5 4 3 8 3 5 4 1 8 5 4...
output:
? 1 1 5 4 ? 6 4 7 6 ? 7 3 8 5 ! 9 5 ? 1 1 2 6 ? 2 7 3 9 ? 3 6 4 8 ? 3 7 4 7 ! 4 7 ? 1 1 5 6 ? 3 6 5 9 ? 4 6 5 8 ? 2 7 3 7 ! 3 8 ? 1 1 7 4 ? 4 5 7 6 ? 2 5 3 7 ? 2 6 2 7 ! 3 7 ? 1 1 2 8 ? 2 9 3 12 ? 1 12 2 14 ? 1 13 2 13 ! 1 13 ? 1 1 4 5 ? 5 3 6 5 ? 6 4 7 6 ! 8 3 ? 1 1 5 6 ? 6 4 8 7 ? 9 5 10 7 ? 10 5 ...
result:
ok Good (50 test cases)
Test #5:
score: 0
Accepted
time: 2ms
memory: 3832kb
input:
50 9 14 5 2 3 2 15 4 9 0 2 2 6 6 2 3 2 10 11 10 0 0 10 3 5 0 2 12 13 12 3 0 2 5 15 3 0 4 1 15 9 12 3 4 2 11 7 4 4 2 3 8 5 2 2 7 7 6 3 2 12 9 10 3 2 1 3 5 3 0 5 3 4 0 10 12 6 6 4 3 7 3 2 4 2 11 11 5 3 4 0 15 8 11 5 2 2 11 11 0 4 4 4 7 14 7 2 0 2 9 8 4 0 4 7 6 6 3 1 6 6 3 3 1 15 4 9 0 2 2 9 11 0 2 3 9...
output:
? 1 1 5 7 ? 6 4 7 7 ? 7 6 8 8 ? 7 4 8 4 ! 8 4 ? 1 1 8 2 ? 5 2 8 3 ? 3 1 4 3 ? 1 1 1 2 ! 1 1 ? 1 1 3 2 ? 2 2 3 4 ? 3 3 4 5 ! 2 5 ? 1 1 5 6 ? 3 4 5 7 ? 2 2 3 4 ! 1 1 ? 1 1 5 2 ? 6 2 8 3 ? 9 1 9 2 ! 9 1 ? 1 1 6 7 ? 4 4 6 7 ? 2 6 3 8 ? 1 4 2 4 ! 1 4 ? 1 1 3 8 ? 3 5 4 8 ? 4 3 5 5 ? 4 3 5 3 ! 5 4 ? 1 1 8 ...
result:
ok Good (50 test cases)
Test #6:
score: 0
Accepted
time: 2ms
memory: 3852kb
input:
50 14 14 6 4 3 3 6 3 0 2 13 6 0 4 4 2 11 13 7 6 2 1 9 4 6 3 1 10 12 6 6 3 1 3 12 0 3 4 1 12 5 0 2 4 2 13 4 8 0 4 1 9 9 0 3 0 10 6 0 2 2 3 5 3 3 6 12 8 4 4 1 7 9 0 2 2 10 11 5 6 2 1 8 5 6 0 1 5 4 3 0 7 5 4 4 3 13 4 8 4 4 2 5 14 9 5 4 2 4 13 7 0 4 1 5 13 3 4 3 10 5 5 4 4 2 9 8 0 2 0 4 12 2 3 3 5 7 3 3...
output:
? 1 1 7 6 ? 4 6 7 10 ? 2 6 3 8 ? 3 7 4 9 ! 3 10 ? 1 1 3 2 ? 4 1 5 3 ! 6 3 ? 1 1 7 3 ? 8 4 10 5 ? 8 2 9 4 ? 8 3 8 4 ! 8 4 ? 1 1 6 7 ? 4 7 6 10 ? 5 7 6 9 ? 3 8 4 8 ! 4 9 ? 1 1 5 2 ? 3 2 5 3 ? 1 1 1 2 ! 2 2 ? 1 1 5 6 ? 3 6 5 9 ? 4 6 5 8 ? 4 8 4 9 ! 5 9 ? 1 1 2 6 ? 2 7 3 9 ? 2 9 3 11 ? 2 10 3 10 ! 3 11 ...
result:
ok Good (50 test cases)
Test #7:
score: 0
Accepted
time: 1ms
memory: 3920kb
input:
50 12 15 0 0 4 4 6 7 4 0 10 5 7 4 4 1 11 9 6 4 3 1 14 5 3 4 4 1 14 8 0 0 2 15 12 6 4 4 2 8 13 10 0 4 2 4 15 2 5 3 2 12 8 0 0 3 1 6 12 0 2 4 1 11 5 6 3 0 13 6 3 5 0 1 11 13 0 3 2 2 9 7 8 0 3 5 13 0 2 4 2 5 6 4 2 2 14 7 0 5 4 1 8 10 8 0 0 13 9 11 0 3 1 10 11 6 4 3 1 8 10 0 3 4 12 6 3 3 3 2 11 13 6 3 2...
output:
? 1 1 6 8 ? 7 9 9 12 ? 10 12 11 14 ? 9 11 10 13 ! 10 13 ? 1 1 3 4 ? 2 4 3 6 ! 1 7 ? 1 1 5 3 ? 3 2 5 3 ? 4 3 5 5 ? 4 2 4 3 ! 5 3 ? 1 1 6 5 ? 7 3 9 6 ? 7 2 8 4 ? 7 1 7 2 ! 8 1 ? 1 1 7 3 ? 4 3 7 4 ? 2 2 3 4 ? 2 3 2 4 ! 3 4 ? 1 1 7 4 ? 8 5 11 6 ? 12 5 13 7 ! 14 7 ? 1 1 8 6 ? 5 7 8 9 ? 3 6 4 8 ? 4 5 5 7 ...
result:
ok Good (50 test cases)
Test #8:
score: 0
Accepted
time: 0ms
memory: 3952kb
input:
50 11 11 0 6 4 2 10 11 6 4 4 2 4 4 0 1 13 12 6 6 4 2 14 9 11 3 3 1 12 5 8 3 2 14 13 0 8 4 4 4 8 0 4 2 14 15 8 8 0 4 14 3 7 5 3 1 13 10 7 4 0 14 10 7 3 4 1 9 6 7 4 0 12 9 10 4 2 5 11 0 4 3 10 5 5 3 4 12 5 3 4 4 2 12 3 7 0 2 12 5 8 3 2 8 14 0 5 4 1 4 15 2 2 3 1 10 6 7 3 2 9 11 5 0 4 2 10 7 5 4 2 4 5 0...
output:
? 1 1 6 5 ? 7 5 9 8 ? 7 5 8 7 ? 6 4 7 6 ! 8 6 ? 1 1 5 6 ? 3 6 5 9 ? 4 8 5 10 ? 4 9 4 10 ! 4 10 ? 1 1 3 2 ? 3 3 4 3 ! 4 4 ? 1 1 7 6 ? 4 7 7 9 ? 6 6 7 8 ? 7 5 8 7 ! 6 7 ? 1 1 7 5 ? 4 3 7 5 ? 6 2 7 4 ? 6 1 6 2 ! 7 1 ? 1 1 6 3 ? 4 2 6 3 ? 2 3 3 5 ! 1 3 ? 1 1 7 6 ? 8 6 11 10 ? 8 6 9 8 ? 7 5 8 7 ! 8 7 ? 1...
result:
ok Good (50 test cases)
Test #9:
score: 0
Accepted
time: 2ms
memory: 3836kb
input:
50 9 10 4 3 4 1 8 7 0 3 0 4 12 7 4 4 1 7 10 5 4 3 14 10 11 3 3 2 3 7 5 0 2 8 15 8 2 2 2 3 14 7 2 3 1 15 3 9 5 3 1 14 3 7 4 3 5 12 3 3 3 4 11 7 0 4 2 10 4 0 3 1 10 12 6 3 0 11 6 3 3 4 1 14 7 7 0 3 1 4 12 2 0 3 5 12 0 2 4 1 8 11 9 0 4 1 5 5 0 2 2 5 8 6 2 1 12 8 4 0 4 1 3 4 3 2 11 10 10 3 4 3 3 4 3 2 4...
output:
? 1 1 4 5 ? 5 3 7 6 ? 7 4 8 6 ? 7 4 8 4 ! 8 5 ? 1 1 4 3 ? 5 3 6 5 ? 4 4 5 6 ! 6 7 ? 1 1 2 6 ? 2 4 3 6 ? 2 5 3 7 ? 1 5 2 5 ! 2 6 ? 1 1 4 5 ? 3 6 4 8 ? 4 5 5 7 ! 4 8 ? 1 1 7 5 ? 4 3 7 5 ? 6 2 7 4 ? 6 1 6 2 ! 6 1 ? 1 1 2 4 ? 2 3 3 5 ? 1 1 2 1 ! 1 1 ? 1 1 4 8 ? 3 9 4 12 ? 2 8 3 10 ? 1 9 2 9 ! 1 9 ? 1 1 ...
result:
ok Good (50 test cases)
Test #10:
score: 0
Accepted
time: 1ms
memory: 3772kb
input:
16 3 3 4 4 2 1 3 3 4 4 2 2 3 3 4 4 2 1 3 3 2 1 2 3 3 4 4 1 2 3 3 2 2 3 3 4 2 2 3 3 4 2 1 3 3 2 1 1 2 3 4 4 4 2 3 4 4 4 1 4 3 4 4 2 4 3 4 4 1 4 3 4 0 4 4 4 4 2 4 4 0 1
output:
? 1 1 3 2 ? 1 1 2 3 ? 1 2 2 2 ? 1 1 1 2 ! 2 2 ? 1 1 3 2 ? 1 1 2 3 ? 1 2 2 2 ? 1 1 1 2 ! 1 2 ? 1 1 3 2 ? 1 1 2 3 ? 1 2 2 2 ? 1 1 1 2 ! 2 2 ? 1 1 3 2 ? 1 2 1 3 ? 2 2 2 3 ! 2 3 ? 1 1 3 2 ? 1 1 2 3 ? 1 2 2 2 ? 1 1 1 2 ! 1 1 ? 1 1 3 2 ? 1 2 1 3 ! 1 3 ? 1 1 3 2 ? 1 1 2 3 ? 2 1 3 1 ! 3 1 ? 1 1 3 2 ? 1 1 2 ...
result:
ok Good (16 test cases)
Test #11:
score: 0
Accepted
time: 130ms
memory: 3908kb
input:
15000 12 8 6 0 0 12 15 8 0 2 1 3 9 0 3 1 11 10 10 0 3 2 3 14 2 4 3 11 9 10 4 2 14 4 7 2 4 1 8 5 0 3 1 11 10 5 4 4 2 8 9 4 4 0 5 12 3 2 4 1 13 9 11 0 0 7 13 4 5 2 2 12 12 6 3 4 2 15 9 12 6 2 4 12 12 5 4 4 2 9 10 5 2 4 1 9 15 8 6 4 2 12 14 12 6 4 3 5 4 0 4 15 9 5 0 3 2 14 7 7 2 4 1 8 15 4 2 0 1 14 11 ...
output:
? 1 1 6 4 ? 7 3 9 4 ? 10 2 11 4 ! 12 1 ? 1 1 6 8 ? 4 9 6 12 ? 2 12 3 14 ? 1 13 2 13 ! 1 14 ? 1 1 2 5 ? 2 5 3 7 ? 2 8 3 8 ! 3 9 ? 1 1 6 5 ? 4 3 6 6 ? 2 2 3 4 ? 2 1 2 2 ! 2 1 ? 1 1 2 7 ? 2 4 3 7 ? 2 2 3 4 ! 3 1 ? 1 1 6 5 ? 4 3 6 6 ? 5 2 6 4 ! 4 2 ? 1 1 7 2 ? 8 2 11 3 ? 8 1 9 3 ? 8 1 8 2 ! 9 1 ? 1 1 4 ...
result:
ok Good (15000 test cases)