QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#301440#2567. Hidden RookzhouhuanyiAC ✓212ms3692kbC++145.7kb2024-01-09 21:22:312024-01-09 21:22:31

Judging History

你现在查看的是最新测评结果

  • [2024-01-09 21:22:31]
  • 评测
  • 测评结果：AC
  • 用时：212ms
  • 内存：3692kb
查看
  • [2024-01-09 21:22:31]
  • 提交

answer

#include<iostream>
#include<cstdio>
using namespace std;
int T,n,m,sx,sy;
int query(int l1,int r1,int l2,int r2)
{
	int d;
	cout<<'?'<<' '<<l1<<' '<<l2<<' '<<r1<<' '<<r2<<endl;
	fflush(stdout);
	cin>>d;
	return d;
}
void solve(int l1,int r1,int l2,int r2)
{
	cerr<<l1<<','<<r1<<':'<<l2<<','<<r2<<endl;
	if (l1==r1&&l2==r2)
	{
		sx=l1,sy=l2;
		return;
	}
	else if (r1-l1==1&&r2-l2==1)
	{
		int d;
		if (l1>=3&&l2!=1)
		{
			d=query(l1-2,l1,l2-1,l2);
			if (d==4) solve(l1,l1,l2,l2);
			else if (d==2) solve(l1,l1,l2+1,l2+1);
			else if (d==3) solve(l1+1,l1+1,l2,l2);
			else solve(l1+1,l1+1,l2+1,l2+1);
		}
		else if (r1<=n-2&&l2!=1)
		{
			d=query(r1,r1+2,l2-1,l2);
			if (d==4) solve(r1,r1,l2,l2);
			else if (d==2) solve(r1,r1,l2+1,l2+1);
			else if (d==3) solve(r1-1,r1-1,l2,l2);
			else solve(r1-1,r1-1,l2+1,l2+1);
		}
		else if (l1>=3&&r2!=m)
		{
			d=query(l1-2,l1,r2,r2+1);
			if (d==4) solve(l1,l1,r2,r2);
			else if (d==2) solve(l1,l1,r2-1,r2-1);
			else if (d==3) solve(l1+1,l1+1,r2,r2);
			else solve(l1+1,l1+1,r2-1,r2-1);
		}
		else if (r1<=n-2&&r2!=m)
		{
			d=query(r1,r1+2,r2,r2+1);
			if (d==4) solve(r1,r1,r2,r2);
			else if (d==2) solve(r1,r1,r2-1,r2-1);
			else if (d==3) solve(r1-1,r1-1,r2,r2);
			else solve(r1-1,r1-1,r2-1,r2-1);
		}
		else if (l1!=1&&l2>=3)
		{
			d=query(l1-1,l1,l2-2,l2);
			if (d==4) solve(l1,l1,l2,l2);
			else if (d==2) solve(l1+1,l1+1,l2,l2);
			else if (d==3) solve(l1,l1,l2+1,l2+1);
			else solve(l1+1,l1+1,l2+1,l2+1);
		}
		else if (r1!=n&&l2>=3)
		{
			d=query(r1,r1+1,l2-2,l2);
			if (d==4) solve(r1,r1,l2,l2);
			else if (d==2) solve(r1-1,r1-1,l2,l2);
			else if (d==3) solve(r1,r1,l2+1,l2+1);
			else solve(r1-1,r1-1,l2+1,l2+1);
		}
		else if (l1!=1&&r2<=m-2)
		{
			d=query(l1-1,l1,r2,r2+2);
			if (d==4) solve(l1,l1,r2,r2);
			else if (d==2) solve(l1+1,l1+1,r2,r2);
			else if (d==3) solve(l1,l1,r2-1,r2-1);
			else solve(l1+1,l1+1,r2-1,r2-1);
		}
		else if (r1!=n&&r2<=m-2)
		{
			d=query(r1,r1+1,r2,r2+2);
			if (d==4) solve(r1,r1,r2,r2);
			else if (d==2) solve(r1-1,r1-1,r2,r2);
			else if (d==3) solve(r1,r1,r2-1,r2-1);
			else solve(r1-1,r1-1,r2-1,r2-1);
		}
		else
		{
			if (query(l1,l1,l2,l2+1)==2)
			{
				if (query(l1+1,l1+1,l2+1,l2+1)==0) solve(l1,l1,l2,l2);
				else solve(l1,l1,l2+1,l2+1);
			}
			else
			{
				if (query(l1,l1,l2+1,l2+1)==0) solve(l1+1,l1+1,l2,l2);
				else solve(l1+1,l1+1,l2+1,l2+1);
			}
		}
	}
	else if (l1==r1)
	{
		int mid=(l2+r2)>>1;
		if (l1!=n)
		{
			if (query(l1,l1+1,l2,mid)==mid-l2+2) solve(l1,r1,l2,mid);
			else solve(l1,r1,mid+1,r2);
		}
		else
		{
			if (query(l1-1,l1,l2,mid)==mid-l2+2) solve(l1,r1,l2,mid);
			else solve(l1,r1,mid+1,r2);
		}
	}
	else if (l2==r2)
	{
		int mid=(l1+r1)>>1;
		if (l2!=m)
		{
			if (query(l1,mid,l2,l2+1)==mid-l1+2) solve(l1,mid,l2,r2);
			else solve(mid+1,r1,l2,r2);
		}
		else
		{
			if (query(l1,mid,l2-1,l2)==mid-l1+2) solve(l1,mid,l2,r2);
			else solve(mid+1,r1,l2,r2);
		}
	}
	else if (r1-l1==1)
	{
		int mid=(l2+r2)>>1;
		if (l1!=n)
		{
			if (query(l1,l1+1,l2,mid)==mid-l2+2) solve(l1,r1,l2,mid);
			else solve(l1,r1,mid+1,r2);
		}
		else
		{
			if (query(l1-1,l1,l2,mid)==mid-l2+2) solve(l1,r1,l2,mid);
			else solve(l1,r1,mid+1,r2);
		}
	}
	else if (r2-l2==1)
	{
		int mid=(l1+r1)>>1;
		if (l2!=m)
		{
			if (query(l1,mid,l2,l2+1)==mid-l1+2) solve(l1,mid,l2,r2);
			else solve(mid+1,r1,l2,r2);
		}
		else
		{
			if (query(l1,mid,l2-1,l2)==mid-l1+2) solve(l1,mid,l2,r2);
			else solve(mid+1,r1,l2,r2);
		}
	}
	else
	{
		int mid1=(l1+r1)>>1,mid2=(l2+r2)>>1,d;
		if (mid1-l1+1!=mid2-l2+1)
		{
			d=query(l1,mid1,l2,mid2);
			if (d==mid1-l1+mid2-l2+1) solve(l1,mid1,l2,mid2);
			else if (d==mid1-l1+1) solve(mid1+1,r1,l2,mid2);
			else if (d==mid2-l2+1) solve(l1,mid1,mid2+1,r2);
			else solve(mid1+1,r1,mid2+1,r2);
		}
		else if (mid1-l1+1!=r2-mid2&&r2-mid2!=1)
		{
			d=query(l1,mid1,mid2+1,r2);
			if (d==mid1-l1+r2-mid2) solve(l1,mid1,mid2+1,r2);
			else if (d==mid1-l1+1) solve(mid1+1,r1,mid2+1,r2);
			else if (d==r2-mid2) solve(l1,mid1,l2,mid2);
			else solve(mid1+1,r1,l2,mid2);
		}
		else if (l1!=1)
		{
			d=query(l1-1,mid1,l2,mid2);
			if (d==mid1-(l1-1)+mid2-l2+1) solve(l1,mid1,l2,mid2);
			else if (d==mid1-(l1-1)+1) solve(mid1+1,r1,l2,mid2);
			else if (d==mid2-l2+1) solve(l1,mid1,mid2+1,r2);
			else solve(mid1+1,r1,mid2+1,r2);
		}
		else if (r1!=n&&r1-mid1!=mid2-l2)
		{
			d=query(mid1+1,r1+1,l2,mid2);
			if (d==(r1+1)-mid1+mid2-l2) solve(mid1+1,r1,l2,mid2);
			else if (d==(r1+1)-mid1) solve(l1,mid1,l2,mid2);
			else if (d==mid2-l2+1) solve(mid1+1,r1,mid2+1,r2);
			else solve(l1,mid1,mid2+1,r2);
		}
		else if (r1-l1+1>4)
		{
		    mid1--,d=query(l1,mid1,l2,mid2);
			if (d==mid1-l1+mid2-l2+1) solve(l1,mid1,l2,mid2);
			else if (d==mid1-l1+1) solve(mid1+1,r1,l2,mid2);
			else if (d==mid2-l2+1) solve(l1,mid1,mid2+1,r2);
			else solve(mid1+1,r1,mid2+1,r2);
		}
		else if (r1-l1==2&&(r2-l2==2||r2-l2==3)&&n>=8)
		{
			if (r1!=n)
			{
				d=query(l1+1,n,r2-1,r2);
				if (d==n-l1+1) solve(l1+1,r1,r2-1,r2);
				else if (d==2) solve(l1+1,r1,l2,r2-2);
				else if (d==n-l1) solve(l1,l1,r2-1,r2);
				else solve(l1,l1,l2,r2-2);
			}
			else
			{
				d=query(1,r1-1,r2-1,r2);
				if (d==l1+2) solve(l1,l1+1,l2,r2-2);
				else if (d==2) solve(l1,l1+1,r2-1,r2);
				else if (d==l1+1) solve(r1,r1,l2,r2-2);
				else solve(r1,r1,r2-1,r2);
			}
		}
		else
		{
			d=query(l1,mid1,1,m);
			if (d==mid1-l1+m) solve(l1,mid1,l2,r2);
			else solve(mid1+1,r1,l2,r2);
		}
	}
	return;
}
int main()
{
	cin>>T;
	while (T--) cin>>n>>m,solve(1,n,1,m),cout<<'!'<<' '<<sx<<' '<<sy<<endl,fflush(stdout);
	return 0;
}
源文件, 语言: C++14

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3560kb

input:

2
6 6
4
2
1
7 5
3
3
3

output:

? 1 1 2 3
? 1 1 2 2
? 1 3 1 4
! 2 3
? 1 1 4 3
? 1 4 2 5
? 2 3 4 4
! 1 4

result:

ok Good (2 test cases)

Test #2:

score: 0
Accepted
time: 1ms
memory: 3688kb

input:

3
15 15
7
0
0
4
3 15
8
5
2
3
15 15
14
0
4
4

output:

? 1 9 8 15
? 5 1 9 4
? 3 5 5 6
? 2 6 4 7
! 2 7
? 1 1 2 8
? 1 9 2 12
? 1 9 2 10
? 2 9 3 11
! 2 12
? 1 9 8 15
? 1 13 4 15
? 4 9 6 10
? 3 8 5 9
! 5 9

result:

ok Good (3 test cases)

Test #3:

score: 0
Accepted
time: 3ms
memory: 3616kb

input:

100
6 6
2
2
1
3 4
2
3
2
7 8
4
2
2
1
5 6
0
0
9 4
5
3
4
11 4
6
4
3
2
15 12
8
3
4
2
5 9
7
0
2
6 7
3
4
3
9 9
4
2
9
2
11 4
6
4
3
2
12 7
4
0
2
14 7
0
4
3
3
9 6
0
4
3
12 11
0
4
0
3 14
7
5
2
3
15 12
0
6
3
4
7 10
8
0
0
15 5
0
4
3
2
11 9
5
4
3
4
14 7
4
5
3
3
15 10
0
4
4
4
7 4
4
2
1
5 13
7
3
3
4
13 8
0
3
2
2
1...

output:

? 1 1 2 3
? 2 1 4 2
? 3 3 3 4
! 4 3
? 1 1 2 4
? 2 1 3 2
? 2 1 3 1
! 3 1
? 1 1 3 4
? 1 1 2 8
? 3 5 4 6
? 3 7 4 7
! 3 8
? 1 1 2 3
? 2 4 4 5
! 5 6
? 1 1 5 2
? 6 1 7 2
? 4 2 6 3
! 6 2
? 1 1 6 2
? 7 1 9 2
? 7 1 8 2
? 5 2 7 3
! 7 1
? 1 1 8 6
? 9 1 12 3
? 8 4 10 5
? 7 3 9 4
! 9 5
? 1 1 3 5
? 1 1 2 3
? 3 4 ...

result:

ok Good (100 test cases)

Test #4:

score: 0
Accepted
time: 3ms
memory: 3560kb

input:

50
9 8
0
3
3
4 11
0
4
3
3
9 11
6
2
9
4
13 8
4
2
2
4
4 15
8
4
3
3
8 9
4
2
2
1
11 12
5
0
3
1
11 14
0
0
3
2
14 14
0
0
4
3
8 3
5
3
0
6 7
6
8
3
3
4 12
6
4
3
0
6 4
4
3
3
9 15
0
2
2
3
12 7
9
0
2
2
13 14
6
6
4
0
12 11
0
3
0
12 13
6
4
4
3
8 5
6
4
2
8 10
5
2
3
2
13 3
7
3
2
2
8 10
0
3
4
15 15
14
4
3
3
8 3
5
2
...

output:

? 1 1 5 4
? 5 5 7 6
? 6 4 8 5
! 9 5
? 1 1 2 6
? 3 7 4 9
? 3 7 4 8
? 1 6 3 7
! 4 7
? 1 1 5 6
? 1 10 3 11
? 2 8 9 9
? 3 7 5 8
! 3 8
? 1 1 7 4
? 1 5 4 6
? 1 7 2 8
? 1 6 3 7
! 3 7
? 1 1 2 8
? 1 9 2 12
? 1 13 2 14
? 2 12 4 13
! 1 13
? 1 1 4 5
? 5 1 6 3
? 7 1 8 2
? 7 3 7 4
! 8 3
? 1 1 5 6
? 5 1 8 3
? 8 4 ...

result:

ok Good (50 test cases)

Test #5:

score: 0
Accepted
time: 2ms
memory: 3632kb

input:

50
9 14
5
2
2
2
15 4
9
5
3
0
6 6
3
3
2
10 11
10
4
3
0
10 3
5
3
2
12 13
12
6
11
1
5 15
3
5
2
0
15 9
12
4
3
4
11 7
4
3
3
4
3 8
5
2
2
7 7
3
4
2
12 9
10
4
3
0
3 5
3
0
5 3
4
3
0
10 12
6
2
3
1
7 3
2
2
2
11 11
10
2
2
2
15 8
11
0
3
2
11 11
6
2
2
2
7 14
7
5
2
3
9 8
4
2
3
4
7 6
6
4
0
6 6
2
3
2
15 4
9
5
3
0
9 ...

output:

? 1 1 5 7
? 6 1 7 4
? 8 1 9 2
? 6 2 8 3
! 8 4
? 1 1 8 2
? 1 1 4 2
? 1 1 2 2
? 2 2 4 3
! 1 1
? 1 1 2 3
? 1 4 2 5
? 2 3 4 4
! 2 5
? 1 1 5 6
? 1 1 2 3
? 1 1 2 2
? 2 2 4 3
! 1 1
? 1 1 5 2
? 6 1 8 2
? 7 2 9 3
! 9 1
? 1 1 6 7
? 1 1 3 4
? 2 3 12 4
? 1 3 2 3
! 1 4
? 1 1 3 8
? 4 1 5 4
? 4 1 5 2
? 2 2 4 3
! 5...

result:

ok Good (50 test cases)

Test #6:

score: 0
Accepted
time: 2ms
memory: 3616kb

input:

50
14 14
7
6
14
4
6 3
0
2
13 6
0
4
3
4
11 13
7
6
4
2
9 4
6
4
3
4
10 12
6
2
0
3 12
0
3
3
1
12 5
0
4
3
2
13 4
8
5
2
2
9 9
5
2
0
10 6
0
2
2
3 5
3
3
6 12
8
0
2
7 9
0
3
2
10 11
5
3
0
8 5
6
3
2
5 4
3
0
7 5
4
4
4
13 4
8
5
3
4
5 14
9
0
3
1
4 13
7
3
3
0
5 13
3
5
3
2
10 5
5
2
3
2
9 8
0
3
0
4 12
2
4
3
2
5 7
3
...

output:

? 1 1 6 7
? 1 8 3 11
? 2 10 14 11
? 3 9 5 10
! 3 10
? 1 1 3 2
? 4 2 5 3
! 6 3
? 1 1 7 3
? 8 4 10 5
? 8 4 9 5
? 6 3 8 4
! 8 4
? 1 1 6 7
? 4 8 7 10
? 3 8 5 9
? 2 7 4 8
! 4 9
? 1 1 5 2
? 1 1 3 2
? 1 1 2 2
? 2 2 4 3
! 2 2
? 1 1 5 6
? 1 7 2 9
? 2 7 4 8
! 5 9
? 1 1 2 6
? 2 7 3 9
? 2 10 3 11
? 2 10 3 10
! ...

result:

ok Good (50 test cases)

Test #7:

score: 0
Accepted
time: 1ms
memory: 3548kb

input:

50
12 15
0
0
4
4
6 7
4
8
2
2
10 5
7
0
1
11 9
6
2
4
0
14 5
3
5
2
4
14 8
0
0
2
2
15 12
6
6
4
4
8 13
10
5
3
4
4 15
2
4
3
4
12 8
0
0
3
0
6 12
0
2
3
1
11 5
6
3
3
13 6
3
4
3
2
11 13
0
4
3
3
9 7
8
4
3
2
5 13
0
4
3
3
5 6
4
3
3
14 7
0
5
3
3
8 10
8
4
3
0
13 9
11
6
4
2
10 11
6
3
0
8 10
0
3
4
12 6
3
4
3
2
11 13...

output:

? 1 1 6 8
? 7 9 9 12
? 9 13 11 14
? 8 12 10 13
! 10 13
? 1 1 3 4
? 1 1 2 7
? 1 5 2 6
? 1 6 1 7
! 1 7
? 1 1 5 3
? 1 1 3 2
? 4 3 4 4
! 5 3
? 1 1 6 5
? 7 4 9 5
? 6 1 8 2
? 5 2 7 3
! 8 1
? 1 1 7 3
? 1 4 4 5
? 1 4 2 5
? 1 3 3 4
! 3 4
? 1 1 7 4
? 8 5 11 6
? 12 7 13 8
? 13 7 14 7
! 14 7
? 1 1 8 6
? 1 7 4 9...

result:

ok Good (50 test cases)

Test #8:

score: 0
Accepted
time: 0ms
memory: 3648kb

input:

50
11 11
0
3
2
1
10 11
6
3
4
4 4
2
2
0
13 12
6
4
4
3
14 9
11
4
3
2
12 5
8
2
3
2
14 13
0
6
2
2
4 8
0
3
4
14 15
8
0
2
4
14 3
7
5
2
3
13 10
7
2
3
2
14 10
7
6
4
3
9 6
7
4
2
1
12 9
10
0
4
4
5 11
0
4
2
2
10 5
5
0
2
12 5
3
3
3
3
12 3
7
4
3
0
12 5
8
2
3
2
8 14
0
5
3
2
4 15
2
4
3
0
10 6
7
2
3
2
9 11
5
2
3
4
...

output:

? 1 7 6 11
? 6 1 9 3
? 6 4 8 5
? 7 6 7 7
! 8 6
? 1 1 5 6
? 1 10 3 11
? 2 9 4 10
! 4 10
? 1 1 2 4
? 3 1 4 2
? 1 2 3 3
! 4 4
? 1 1 7 6
? 1 7 4 9
? 4 7 6 8
? 3 6 5 7
! 6 7
? 1 1 7 5
? 1 1 4 3
? 4 1 6 2
? 7 1 8 1
! 7 1
? 1 1 6 3
? 1 1 3 2
? 1 3 2 4
? 1 3 1 4
! 1 3
? 1 8 7 13
? 8 5 11 7
? 7 5 9 6
? 8 7 8...

result:

ok Good (50 test cases)

Test #9:

score: 0
Accepted
time: 2ms
memory: 3692kb

input:

50
9 10
4
3
2
8 7
4
2
1
4 12
7
3
2
1
7 10
5
2
2
1
14 10
11
4
4
0
3 7
5
3
0
8 15
8
5
3
3
3 14
7
5
2
0
15 3
9
4
3
3
14 3
7
4
2
1
5 12
3
4
3
2
4 11
7
4
3
3
10 4
0
3
3
10 12
6
4
2
2
11 6
3
4
2
2
14 7
7
4
3
0
4 12
2
4
3
0
5 12
0
4
3
0
8 11
9
4
2
1
5 5
0
2
1
5 8
6
9
2
0
12 8
4
2
2
2
3 4
5
2
0
11 10
10
4
2...

output:

? 1 1 4 5
? 5 4 7 5
? 6 3 8 4
! 8 5
? 1 5 4 7
? 4 5 6 6
? 5 6 5 7
! 6 7
? 1 1 2 6
? 1 1 2 3
? 1 4 2 5
? 1 6 1 7
! 2 6
? 1 1 4 5
? 1 6 2 8
? 3 6 4 7
? 3 8 3 9
! 4 8
? 1 1 7 5
? 1 1 4 3
? 4 1 6 2
? 3 2 5 3
! 6 1
? 1 1 2 4
? 1 1 2 2
? 2 2 3 4
! 1 1
? 1 1 4 8
? 1 9 2 12
? 1 9 2 10
? 2 8 4 9
! 1 9
? 1 1 ...

result:

ok Good (50 test cases)

Test #10:

score: 0
Accepted
time: 1ms
memory: 3600kb

input:

16
3 3
4
3
1
1
3 3
4
3
2
1
3 3
4
3
1
1
3 3
4
2
1
3 3
4
3
2
0
3 3
4
2
2
3 3
2
3
2
3 3
2
3
1
3 3
2
2
3 4
5
3
4
3 4
5
2
4
4 3
4
3
4
4 3
2
3
4
4 3
4
3
0
4 4
5
3
4
4 4
2
2
0

output:

? 1 1 2 3
? 1 1 2 2
? 1 1 1 2
? 1 2 1 2
! 2 2
? 1 1 2 3
? 1 1 2 2
? 1 1 1 2
? 2 2 2 2
! 1 2
? 1 1 2 3
? 1 1 2 2
? 1 1 1 2
? 1 2 1 2
! 2 2
? 1 1 2 3
? 1 1 2 2
? 1 2 1 3
! 2 3
? 1 1 2 3
? 1 1 2 2
? 1 1 1 2
? 2 2 2 2
! 1 1
? 1 1 2 3
? 1 1 2 2
? 1 2 1 3
! 1 3
? 1 1 2 3
? 2 1 3 2
? 2 1 3 1
! 3 1
? 1 1 2 ...

result:

ok Good (16 test cases)

Test #11:

score: 0
Accepted
time: 212ms
memory: 3636kb

input:

15000
12 8
6
3
2
2
12 15
8
4
11
2
3 9
0
2
1
11 10
10
2
2
2
3 14
2
5
3
2
11 9
10
0
4
4
14 4
7
5
3
0
8 5
0
3
0
11 10
5
3
3
3
8 9
4
4
2
1
5 12
3
3
2
1
13 9
11
6
3
0
7 13
4
4
3
0
12 12
5
0
4
0
15 9
12
0
3
0
12 12
6
0
3
2
9 10
5
4
3
2
9 15
8
3
3
4
12 14
12
0
3
1
5 4
0
4
15 9
5
2
2
2
14 7
7
5
3
3
8 15
4
0...

output:

? 1 1 6 4
? 7 1 9 2
? 10 1 11 2
? 11 1 12 1
! 12 1
? 1 1 6 8
? 1 9 3 12
? 2 14 12 15
? 1 14 2 14
! 1 14
? 1 1 2 5
? 2 6 3 7
? 2 8 3 8
! 3 9
? 1 1 6 5
? 1 4 3 5
? 2 2 11 3
? 2 1 2 2
! 2 1
? 1 1 2 7
? 2 1 3 4
? 2 1 3 2
? 2 1 3 1
! 3 1
? 1 1 6 5
? 1 4 3 5
? 3 1 5 2
? 2 2 4 3
! 4 2
? 1 1 7 2
? 8 1 11 2
...

result:

ok Good (15000 test cases)
English 繁體中文 简体中文

伺服器時間: 2025-02-01 17:52:22 | 開源專案