QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#846031#2567. Hidden RookBreakPlusAC ✓1884ms238696kbC++144.8kb2025-01-06 21:17:192025-01-06 21:17:20

Judging History

This is the latest submission verdict.

  • [2025-01-06 21:17:20]
  • Judged
  • Verdict: AC
  • Time: 1884ms
  • Memory: 238696kb
  • [2025-01-06 21:17:19]
  • Submitted

answer

#include <bits/stdc++.h>
#pragma GCC optimize(3, "Ofast", "inline", "unroll-loops")
using namespace std;
#define fi first
#define se second
#define mkp make_pair
typedef pair<int,int> P;
typedef long long ll;
const int N = 15;
int T, n, m, x, y, askCnt;

bool rev;
int dp[17][17][17][17][17][17];
tuple<int,int,int,int> jc[17][17][17][17][17][17];
inline int ask(int l1, int r1, int l2, int r2) {
	if(rev) swap(l1,l2), swap(r1,r2);
#ifdef LOCAL
	++askCnt;
	int res = 0;
	for (int i = l1; i <= r1; ++i) {
		for (int j = l2; j <= r2; ++j) {
			if (x == i || y == j) {
				++res;
			}
		}
	}
	// cout<<"val = "<<res<<endl;
	return res;
#else
	cout << "? " << l1 << " " << l2 << " " << r1 << " " << r2 << endl;
	int res;
	cin >> res;
	return res;
#endif
}

inline void print_ans(int ansX, int ansY) {
	if(rev) swap(ansX, ansY);
#ifndef LOCAL
	cout << "! " << ansX << " " << ansY << endl;
#else
	assert(ansX == x && ansY == y && askCnt <= 4);
#endif
}

mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
ll rng(ll x,ll y){ return x+rnd()%(y-x+1); }
inline void init() {
	askCnt = 0;
	n = rng(3, 15), m = rng(3, 15);
	x = rng(1, n), y = rng(1, m);
	// n = 6, m = 7, x = 1, y = 3;
	// n = 3, m = 3, x = 2, y = 2;
}

inline P operator| (P A, P B){
	if(A.fi > A.se) return B;
	if(B.fi > B.se) return A;
	return {min(A.fi,B.fi), max(A.se,B.se)};
}
inline P operator& (P A, P B){
	return {max(A.fi,B.fi), min(A.se,B.se)};
}
inline tuple<int,int,int,int> songke(int l1,int r1,int l2,int r2,int x1,int y1,int x2,int y2,int val){
	int X = y1-x1+1, Y = y2-x2+1;
	bool s1 = (x1==y1), s2 = (x2==y2);
	P m1 = {l1, r1}, m2 = {l2, r2};

	if((!s1 && !s2) || (s1 && val != Y) || (s2 && val != X)){
		bool f1 = (val==Y || val==X+Y-1), f2 = (val==X || val==X+Y-1);
		if(f1) m1 = m1 & mkp(x1, y1);
		else{
			m1 = m1 & (mkp(l1, x1-1) | mkp(y1+1, r1));
		}
		if(f2) m2 = m2 & mkp(x2, y2); else m2 = m2 & (mkp(l2, x2-1) | mkp(y2+1, r2));
	}else if(s1 && val == Y) m1 = m1 & mkp(x1, y1);
	else m2 = m2 & mkp(x2, y2);
	return {m1.fi, m1.se, m2.fi, m2.se};
}
inline void solve() {
#ifdef LOCAL
	init();
	// cout<<"Q "<<n<<" "<<m<<" "<<x<<" "<<y<<endl;
#else
	cin >> n >> m;
#endif

	if(n > m) swap(n, m), rev = 1; else rev = 0;
	int l1=1, r1=n, l2=1, r2=m;
	int C = 0;
	while(r1>l1 || r2>l2){
		auto [x1,y1,x2,y2] = jc[n][m][l1][r1][l2][r2];
		int ret = ask(x1, y1, x2, y2);
		auto [a,b,c,d] = songke(l1,r1,l2,r2,x1,y1,x2,y2,ret);
		l1=a,r1=b,l2=c,r2=d;
		// cout<<l1<<","<<r1<<" "<<l2<<","<<r2<<endl;
		C ++;
		if(C > 10) break;
	}
	print_ans(l1, l2);
}

void chkmin(int &a,int b){ a=min(a,b); }

inline void solve(int p,int q,int l1,int r1,int l2,int r2,int x1,int y1,int x2,int y2){
	int w = 0, X = y1-x1+1, Y = y2-x2+1;
	if(X == Y) return;
	for(int val: {0, X, Y, X+Y-1}){
		auto [a,b,c,d] = songke(l1,r1,l2,r2,x1,y1,x2,y2,val);
		w = max(w, dp[p][q][a][b][c][d] + 1);
	}
	if(dp[p][q][l1][r1][l2][r2] > w){
		dp[p][q][l1][r1][l2][r2] = w;
		jc[p][q][l1][r1][l2][r2] = {x1, y1, x2, y2};
	}
}
int main() {
	#ifdef LOCAL
		assert(freopen("input.txt","r",stdin));
		assert(freopen("output.txt","w",stdout));
	#endif
	memset(dp, 0x3f, sizeof(dp));
	for(int p=3;p<=15;p++)
		for(int q=p;q<=15;q++){
			for(int i=0;i<=p+1;i++) for(int ii=0;ii<i;ii++)
			for(int j=0;j<=q+1;j++) for(int jj=0;jj<=q+1;jj++)
				dp[p][q][i][ii][j][jj]=0;
			for(int i=0;i<=p+1;i++) for(int ii=0;ii<=p+1;ii++)
			for(int j=0;j<=q+1;j++) for(int jj=0;jj<j;jj++)
				dp[p][q][i][ii][j][jj]=0;
			for(int i=1;i<=p;i++) for(int j=1;j<=q;j++) dp[p][q][i][i][j][j] = 0;
			for(int l1=p;l1>=1;l1--) for(int r1=l1;r1<=p;r1++)
			for(int l2=q;l2>=1;l2--) for(int r2=l2;r2<=q;r2++){

				if(p<15){
					for(int x1:{1})
					for(int y1=x1;y1<=r1;y1++){
						for(int x2:{1,l2})
						for(int y2=x2;y2<=r2;y2++)
							solve(p,q,l1,r1,l2,r2,x1,y1,x2,y2);
					}

					for(int y1:{p})
					for(int x1=y1;x1>=1;x1--){
						for(int y2:{q})
						for(int x2=y2;x2>=1;x2--)
							solve(p,q,l1,r1,l2,r2,x1,y1,x2,y2);
					}
				}else{
					for(int x1=1;x1<=l1;x1++)
					for(int y1=x1;y1<=p;y1++){
						for(int x2=1;x2<=l2;x2++)
						for(int y2=x2;y2<=q;y2++)
							solve(p,q,l1,r1,l2,r2,x1,y1,x2,y2);
						for(int x2=1;x2<=q;x2++)
						for(int y2=max(x2,r2);y2<=q;y2++)
							solve(p,q,l1,r1,l2,r2,x1,y1,x2,y2);
					}

					for(int x1=1;x1<=p;x1++)
					for(int y1=max(r1,x1);y1<=p;y1++){
						for(int x2=1;x2<=l2;x2++)
						for(int y2=x2;y2<=q;y2++)
							solve(p,q,l1,r1,l2,r2,x1,y1,x2,y2);
						// for(int x2=1;x2<=q;x2++)
						// for(int y2=max(x2,r2);y2<=q;y2++)
						// 	solve(p,q,l1,r1,l2,r2,x1,y1,x2,y2);
					}
				}
			}
			// cout<<"dp "<<p<<" "<<q<<" = "<<dp[p][q][1][p][1][q]<<endl;
		}
	cerr<<"solved"<<endl;
#ifdef LOCAL
	T = 15000;
#else
	cin >> T;
#endif
	while (T--) {
		solve();
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1771ms
memory: 238084kb

input:

2
6 6
4
1
8
7 5
2
5
6

output:

? 1 1 2 3
? 1 1 2 1
? 2 3 6 6
! 2 3
? 1 1 3 2
? 1 1 2 4
? 2 4 7 5
! 1 4

result:

ok Good (2 test cases)

Test #2:

score: 0
Accepted
time: 1750ms
memory: 238072kb

input:

3
15 15
14
4
6
8
3 15
7
5
1
1
15 15
8
3
13
0

output:

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

result:

ok Good (3 test cases)

Test #3:

score: 0
Accepted
time: 1772ms
memory: 235084kb

input:

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

output:

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

result:

ok Good (100 test cases)

Test #4:

score: 0
Accepted
time: 1740ms
memory: 238696kb

input:

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

output:

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

result:

ok Good (50 test cases)

Test #5:

score: 0
Accepted
time: 1756ms
memory: 238452kb

input:

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

output:

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

result:

ok Good (50 test cases)

Test #6:

score: 0
Accepted
time: 1749ms
memory: 238624kb

input:

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

output:

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

result:

ok Good (50 test cases)

Test #7:

score: 0
Accepted
time: 1746ms
memory: 236748kb

input:

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

output:

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

result:

ok Good (50 test cases)

Test #8:

score: 0
Accepted
time: 1754ms
memory: 234952kb

input:

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

output:

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

result:

ok Good (50 test cases)

Test #9:

score: 0
Accepted
time: 1765ms
memory: 236276kb

input:

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

output:

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

result:

ok Good (50 test cases)

Test #10:

score: 0
Accepted
time: 1741ms
memory: 238448kb

input:

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

output:

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

result:

ok Good (16 test cases)

Test #11:

score: 0
Accepted
time: 1884ms
memory: 237752kb

input:

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

output:

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

result:

ok Good (15000 test cases)