QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#497261#2567. Hidden RookzjjwsAC ✓130ms3952kbC++145.9kb2024-07-28 21:48:432024-07-28 21:48:44

Judging History

This is the latest submission verdict.

  • [2024-07-28 21:48:44]
  • Judged
  • Verdict: AC
  • Time: 130ms
  • Memory: 3952kb
  • [2024-07-28 21:48:43]
  • Submitted

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)