QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#827391#2567. Hidden RookZi_GaoAC ✓69ms4056kbC++201.4kb2024-12-22 22:25:592024-12-22 22:25:59

Judging History

This is the latest submission verdict.

  • [2024-12-22 22:25:59]
  • Judged
  • Verdict: AC
  • Time: 69ms
  • Memory: 4056kb
Show
  • [2024-12-22 22:25:59]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;struct N{int l,r;N(){};N(int _l,int _r){l=_l,r=_r;};int mid(){return(l+r)>>1;}int le(){return r-l+1;}N operator-(const N&o)const{if(o.l<=l)return{o.r+1,r};else return{l,o.l-1};}N operator&(const N&o)const{return{max(l,o.l),min(r,o.r)};}};N nx,ny;int n,m,mid,res,lx,ly,T;int qry(N qx,N qy){printf("? %d %d %d %d\n",qx.l,qy.l,qx.r,qy.r);fflush(stdout);scanf("%d",&res);return res;}void solve(){scanf("%d%d",&n,&m);nx={1,n};ny={1,m};if(nx.le()<=4&&ny.le()<=4){while(nx.le()>1){mid=nx.mid();N t(nx.l,mid);res=qry(t,{1,m});if(res==t.le()+m-1)nx.r=mid;else nx.l=mid+1;}while(ny.le()>1){mid=ny.mid();N t(ny.l,mid);res=qry({1,n},t);if(res==t.le()+n-1)ny.r=mid;else ny.l=mid+1;}}else{while(nx.le()>1||ny.le()>1){vector<N>vx,vy;auto addnod=[&](vector<N>&vec,N now,int n){mid=now.mid();if(1<mid)vec.push_back({1,mid});if(2<mid&&2<=now.l)vec.push_back({2,mid});if(mid+1<n)vec.push_back({mid+1,n});if(mid+1<n-1&&now.r<=n-1)vec.push_back({mid+1,n-1});return;};addnod(vx,nx,n);addnod(vy,ny,m);if(n==m&&nx.l==1&&nx.r==n&&ny.l==1&&ny.r==m)vx.push_back({1,nx.mid()+1});for(auto qx:vx)for(auto qy:vy)if(qx.le()!=qy.le()){res=qry(qx,qy),lx=qx.le(),ly=qy.le();if(res==lx+ly-1||res==ly)nx=nx&qx;else nx=nx-qx;if(res==lx+ly-1||res==lx)ny=ny&qy;else ny=ny-qy;goto loop;}loop:;}}printf("! %d %d\n",nx.l,ny.l);fflush(stdout);}int main(){T;scanf("%d",&T);while(T--)solve();return 0;}
源文件, 语言: C++20

详细

Test #1:

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

input:

2
6 6
6
5
7
7 5
3
5
6

output:

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

result:

ok Good (2 test cases)

Test #2:

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

input:

3
15 15
7
14
6
20
3 15
8
13
10
11
15 15
14
4
15
13

output:

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

result:

ok Good (3 test cases)

Test #3:

score: 0
Accepted
time: 5ms
memory: 3772kb

input:

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

output:

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

result:

ok Good (100 test cases)

Test #4:

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

input:

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

output:

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

result:

ok Good (50 test cases)

Test #5:

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

input:

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

output:

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

result:

ok Good (50 test cases)

Test #6:

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

input:

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

output:

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

result:

ok Good (50 test cases)

Test #7:

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

input:

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

output:

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

result:

ok Good (50 test cases)

Test #8:

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

input:

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

output:

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

result:

ok Good (50 test cases)

Test #9:

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

input:

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

output:

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

result:

ok Good (50 test cases)

Test #10:

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

input:

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

output:

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

result:

ok Good (16 test cases)

Test #11:

score: 0
Accepted
time: 69ms
memory: 3772kb

input:

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

output:

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

result:

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

服务器时间: 2025-02-08 16:12:18 | 开源项目