QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#36051#2567. Hidden Rookconqueror_of_zky#AC ✓739ms3740kbC++145.1kb2022-06-23 16:36:502022-06-23 16:36:52

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-06-23 16:36:52]
  • Judged
  • Verdict: AC
  • Time: 739ms
  • Memory: 3740kb
Show
  • [2022-06-23 16:36:50]
  • Submitted

answer

#include <bits/stdc++.h>
#define mod 1000000007
using namespace std;
int n,m,CNT=0,TEST=0,PR=0;
int ansx,ansy,ban[16][16],FLAG;
inline int cal(int x,int y,int lx,int ly,int rx,int ry)
{
	int rtn=0;
	for(int i=lx;i<=rx;i++)
	{
		for(int j=ly;j<=ry;j++)
		{
			if(i==x||j==y) ++rtn;
		}
	}
	return rtn;
}
inline int ask(int lx,int ly,int rx,int ry)
{
	if(lx>rx) swap(lx,rx);
	if(ly>ry) swap(ly,ry);
	if(FLAG) cout << "? " << ly << " " << lx << " " << ry << " " << rx << endl;
	else cout << "? " << lx << " " << ly << " " << rx << " " << ry << endl;
	if(lx<1||rx>n||ly<1||ry>m) exit(1);
	++CNT;
	if(!TEST)
	{
		cin >> lx;
		return lx;
	}
	else return cal(ansx,ansy,lx,ly,rx,ry);
}
inline void ASK(int l1,int l2,int r1,int r2)
{
	if(l1>r1) swap(l1,r1);
	if(l2>r2) swap(l2,r2);
	int rtn=ask(l1,l2,r1,r2);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(!ban[i][j]&&cal(i,j,l1,l2,r1,r2)!=rtn) ban[i][j]=1;
}
inline bool check(int x,int y)
{
	return x<=n&&x>=1&&y<=m&&y>=1;
}
inline void solve(int l1,int l2,int r1,int r2)
{
	if(l1==r1&&l2==r2)
	{
		if(!FLAG) cout << "! " << l1 << " " << l2 << endl;
		else cout << "! " << l2 << " " << l1 << endl;
		return ;
	}
	int lenx=r1-l1+1,leny=r2-l2+1;
	int A=(lenx+1)/2,B=(leny+1)/2;
	if(lenx==2&&leny==2)
	{
		if(check(l1-1,l2-2)) ASK(l1-1,l2-2,l1,l2);
		else if(check(l1-2,l2-1)) ASK(l1-2,l2-1,l1,l2);
		else if(check(r1+1,l2-2)) ASK(r1+1,l2-2,r1,l2);
		else if(check(r1+2,l2-1)) ASK(r1+2,l2-1,r1,l2);
		else if(check(l1-1,r2+2)) ASK(l1-1,r2+2,l1,r2);
		else if(check(l1-2,r2+1)) ASK(l1-2,r2+1,l1,r2);
		else if(check(r1+1,r2+2)) ASK(r1+1,r2+2,r1,r2);
		else if(check(r1+2,r2+1)) ASK(r1+2,r2+1,r1,r2);
		int x=100,y=100,X=0,Y=0;
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				if(!ban[i][j])
				{
					x=min(x,i);
					X=max(X,i);
					y=min(y,j);
					Y=max(Y,j);
				}
		//		cout << ban[i][j];
			}
		//	cout << "\n";
		}
		solve(x,y,X,Y);
		return ;
	}
	if(lenx==1&&leny==2)
	{
		ASK(1,l2,n,l2);
		int x=100,y=100,X=0,Y=0;
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				if(!ban[i][j])
				{
					x=min(x,i);
					X=max(X,i);
					y=min(y,j);
					Y=max(Y,j);
				}
		if(PR)		cout << ban[i][j];
			}
		if(PR)	cout << "\n";
		}
		solve(x,y,X,Y);
		return ;
	}
	if(leny==1&&lenx==2)
	{
		ASK(l1,1,l1,m);
		int x=100,y=100,X=0,Y=0;
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				if(!ban[i][j])
				{
					x=min(x,i);
					X=max(X,i);
					y=min(y,j);
					Y=max(Y,j);
				}
	if(PR)			cout << ban[i][j];
			}
	if(PR)		cout << "\n";
		}
		solve(x,y,X,Y);
		return ;
	}
	if(CNT==0)
	{
		A=(lenx)/2,B=(leny)/2;
		if(A==1) ++A;
		if(B==1) ++B;
		if(A==B)
		{
			if(lenx<leny) ++A;
			else ++B;
		}
		ASK(l1,l2,l1+A-1,l2+B-1);
		int x=100,y=100,X=0,Y=0;
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				if(!ban[i][j])
				{
					x=min(x,i);
					X=max(X,i);
					y=min(y,j);
					Y=max(Y,j);
				}
	if(PR)			cout << ban[i][j];
			}
	if(PR)		cout << "\n";
		}
		solve(x,y,X,Y);
		return ;
	}
		int a=l1,b=l2,c=l1+A-1,d=l2+B-1;
		if(A==1)
		{
			if(a!=1) a=1;
			else
			{
				a=r1-A+1,b=r2-B+1,c=r1,d=r2;
				if(c!=n) c=n;
			}
			A=c-a+1;
		}
		if(B==1)
		{
			if(b!=1) b=1;
			else
			{
				a=r1-A+1,b=r2-B+1,c=r1,d=r2;
				if(d!=n) d=m;
			}
			B=d-b+1;
		}
		if(A==B)
		{
			if(a!=1) a=1;
			else if(b!=1) b=1;
			else
			{
				a=r1-A+1,b=r2-B+1,c=r1,d=r2;
				if(c!=n) c=n;
				else if(d!=m) d=m;
			}
		}
		ASK(a,b,c,d);
		int x=100,y=100,X=0,Y=0;
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				if(!ban[i][j])
				{
					x=min(x,i);
					X=max(X,i);
					y=min(y,j);
					Y=max(Y,j);
				}
	if(PR)			cout << ban[i][j];
			}
	if(PR)		cout << "\n";
		}
		solve(x,y,X,Y);
		return ;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T;
	cin >> T;
	while(T--)
	{
		cin >> n >> m;
		memset(ban,0,sizeof ban);
		if(TEST) cin >> ansx >> ansy;
		if(n>m) swap(n,m),swap(ansx,ansy),FLAG=1;
		else FLAG=0;
				//	if(TEST) cin >> ansx >> ansy;
					if(n==3&&m==3)
					{
						ASK(1,1,2,2);
						ASK(1,2,2,3);
						ASK(2,1,3,2);
						ASK(2,2,3,3);
						for(int i=1;i<=n;i++)
						{
							for(int j=1;j<=m;j++)
							{
								if(!ban[i][j])
								{
									cout << "! " << i << " " << j << endl;
								}
							}
						}
						continue;
					}
					CNT=0;
					solve(1,1,n,m);
					if(CNT>4) exit(1);
	}
/*	for(n=3;n<=15;n++)
	{
		for(m=n;m<=15;m++)
		{
			for(ansx=1;ansx<=n;ansx++)
			{
				for(ansy=1;ansy<=m;ansy++)
				{
					cout << n << "!!" << m << "!!" << ansx << "!!" << ansy << "!!\n";
					memset(ban,0,sizeof ban);
				//	if(TEST) cin >> ansx >> ansy;
					if(n==3&&m==3)
					{
						ASK(1,1,2,2);
						ASK(1,2,2,3);
						ASK(2,1,3,2);
						ASK(2,2,3,3);
						for(int i=1;i<=n;i++)
						{
							for(int j=1;j<=m;j++)
							{
								if(!ban[i][j])
									cout << "! " << i << " " << j << endl;
							}
						}
						continue;
					}
					CNT=0;
					solve(1,1,n,m);
					if(CNT>4) exit(1);
				}
			}
		}
	}*/
	return 0;
}
源文件, 语言: C++14

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 3604kb

input:

2
6 6
6
6
4
7 5
2
5
0

output:

? 1 1 3 4
? 2 3 6 4
? 1 1 2 3
! 2 3
? 1 1 3 2
? 1 1 2 4
? 2 2 4 3
! 1 4

result:

ok Good (2 test cases)

Test #2:

score: 0
Accepted
time: 4ms
memory: 3672kb

input:

3
15 15
14
12
6
4
3 15
7
5
14
3
15 15
8
4
7
4

output:

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

result:

ok Good (3 test cases)

Test #3:

score: 0
Accepted
time: 16ms
memory: 3704kb

input:

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

output:

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

result:

ok Good (100 test cases)

Test #4:

score: 0
Accepted
time: 7ms
memory: 3740kb

input:

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

output:

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

result:

ok Good (50 test cases)

Test #5:

score: 0
Accepted
time: 6ms
memory: 3612kb

input:

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

output:

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

result:

ok Good (50 test cases)

Test #6:

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

input:

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

output:

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

result:

ok Good (50 test cases)

Test #7:

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

input:

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

output:

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

result:

ok Good (50 test cases)

Test #8:

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

input:

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

output:

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

result:

ok Good (50 test cases)

Test #9:

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

input:

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

output:

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

result:

ok Good (50 test cases)

Test #10:

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

input:

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

output:

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

result:

ok Good (16 test cases)

Test #11:

score: 0
Accepted
time: 739ms
memory: 3672kb

input:

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

output:

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

result:

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

伺服器時間: 2025-02-08 17:20:08 | 開源專案