QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#846031 | #2567. Hidden Rook | BreakPlus | AC ✓ | 1884ms | 238696kb | C++14 | 4.8kb | 2025-01-06 21:17:19 | 2025-01-06 21:17:20 |
Judging History
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;
}
詳細信息
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)