[BalticOI 2018] 蠕虫之忧
题目描述
题目译自 BalticOI 2018 Day1「Worm Worries」
本题是一道交互题。
在一个三维空间（我们限制大小为 N × M × K N\times M\times K N×M×K）内，每个点都有一个正整数参数，记这个参数为 H [ x , y , z ] H[x,\, y,\, z] H[x,y,z]（保证 1 1 1 ⩽ \leqslant ⩽ x x x ⩽ \leqslant ⩽ N N N , , , 1 1 1 ⩽ \leqslant ⩽ y y y ⩽ \leqslant ⩽ M M M , , , 1 1 1 ⩽ \leqslant ⩽ z z z ⩽ \leqslant ⩽ K K K 且每个参数都不超过 1 0 9 10^9 109）。你最多可以询问 Q Q Q 次，找到一个点，使得这个点的参数大于它周围与它有公共边的所有点的参数，即： H [ x , y , z ] ⩾ max ( H [ x + 1 , y , z ] , H[x,\,y,\,z]\geqslant\max(H[x+1,\,y,\,z], H[x,y,z]⩾max(H[x+1,y,z], H [ x − 1 , y , z ] , H[x-1,\,y,\,z], H[x−1,y,z], H [ x , y − 1 , z ] , H[x,\,y-1,\,z], H[x,y−1,z], H [ x , y − 1 , z ] , H[x,\,y-1,\,z], H[x,y−1,z], H [ x , y , z + 1 ] , H[x,\,y,\,z+1], H[x,y,z+1], H [ x , y , z − 1 ] ) . H[x,\,y,\,z-1]). H[x,y,z−1]).
特别地，当一个点不在空间直角坐标系的第一卦限内时，它的参数为 0 0 0。
输入格式
请使用标准输入输出流与交互库进行交互。你可以向交互库询问最多 Q Q Q 次，每次可以询问一个点的参数。
输入的第一行包含四个整数
N
,
M
,
K
,
Q
N,\,M,\,K,\,Q
N,M,K,Q （请忽略这一行的其他参数）。在此之后，你可以向交互器提出至多
Q
Q
Q 行形如 ? x y z 的询问，表示“询问坐标为
(
x
,
y
,
z
)
(x,\,y,\,z)
(x,y,z) 的点的参数是多少”。对于每一组询问，交互器会输出一行一个整数表示坐标为
(
x
,
y
,
z
)
(x,\,y,\,z)
(x,y,z) 的点的参数。
当你找到一组解时，输出一行 ! x y z 表示你找到的答案是
(
x
,
y
,
z
)
(x,\,y,\,z)
(x,y,z)，并终止程序。此时交互器不会有任何输出。
所有坐标必须满足
1
⩽
x
⩽
N
,
1
⩽
y
⩽
M
,
1
⩽
z
⩽
K
1\leqslant x\leqslant N,\, 1\leqslant y\leqslant M,\, 1\leqslant z\leqslant K
1⩽x⩽N,1⩽y⩽M,1⩽z⩽K。如果不满足坐标的限制、询问不符合格式或询问超过了
Q
Q
Q 行，交互器会输出 -1 并退出，此时你的程序也应该退出。否则你可能会得到 Runtime Error 或 Time Limit Exceeded 的判定结果。
请注意，你必须在每一次询问之后手动刷新缓存，否则你的程序将会超时，对于各语言，刷新缓存的方法如下：
- Java: 调用
System.out.println()会自动刷新缓存； - Python: 调用
print()会自动刷新缓存； - C++:
cout << endl可以输出一个换行并刷新缓存。如果使用printf，请使用fflush(stdout)； - Pascal: 调用
Flush(Output)。
为了帮助你更好地完成交互，我们提供了可以复制到你的程序里的可选代码。可选代码使用了较快的输入输出，可能会提高 IO 较慢的 Python 和 Java 语言的程序效率（只与最后两个子任务有关）。
交互器没有使用随机函数，这意味着，每组测试数据都是固定的，与你的程序的询问无关。
输出格式
为了使你更好地完成交互，下面给出一组交互的示例。在这个示例中，
N
=
3
,
M
=
3
,
K
=
1
,
Q
=
3
N=3,\,M=3,\,K=1,\,Q=3
N=3,M=3,K=1,Q=3，这三个格子的参数为
{
10
,
14
,
13
}
\{10,\,14,\,13\}
{10,14,13}。以 JUDGE 开头的行表示交互库输出的内容（你的程序的标准输入的内容），以 YOU 开头的行表示你的程序的输出。
JUDGE: 3 1 1 3 123123 fixed 10 14 13
YOU : ? 3 1 1
JUDGE: 13
YOU : ? 2 1 1
JUDGE: 14
YOU : ? 1 1 1
JUDGE: 10
YOU : ! 2 1 1
提示
| 子任务 | 分值 | 限制 |
|---|---|---|
| 1 1 1 | 10 10 10 | M = K = 1 , N = 1 000 000 , Q = 10 000 M=K=1,\,N=1\,000\,000,\,Q=10\,000 M=K=1,N=1000000,Q=10000 |
| 2 2 2 | 22 22 22 | M = K = 1 , N = 1 000 000 , Q = 35 M=K=1,\,N=1\,000\,000,\,Q=35 M=K=1,N=1000000,Q=35 |
| 3 3 3 | 12 12 12 | K = 1 , N = M = 200 , Q = 4 000 K=1,\,N=M=200,\,Q=4\,000 K=1,N=M=200,Q=4000 |
| 4 4 4 | 19 19 19 | K = 1 , N = M = 1 000 , Q = 3 500 K=1,\,N=M=1\,000,\,Q=3\,500 K=1,N=M=1000,Q=3500 |
| 5 5 5 | 14 14 14 | N = M = K = 100 , Q = 100 000 N=M=K=100,\,Q=100\,000 N=M=K=100,Q=100000 |
| 6 6 6 | 23 23 23 | N = M = K = 500 , Q = 150 000 N=M=K=500,\,Q=150\,000 N=M=K=500,Q=150000 |
感谢 Hatsune_Miku 提供的翻译
#include<bits/stdc++.h>
#define Gc() getchar()
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define PB push_back
using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned ll;
using namespace std;const int N=2666+5,M=170+5,K=1e5+5,mod=998244353,Mod=mod-1;const ll INF=1e18+7;const db eps=1e-5;mt19937 rnd(time(0));
int n,m,k,Q;map<int,int> f;
int GI(int x,int y,int z){return (x-1)*m*k+(y-1)*k+z-1;}
int Qry(int x,int y,int z){if(x<1||y<1||z<1||x>n||y>m||z>k) return 0;int Id=GI(x,y,z);if(f.count(Id))return f[Id];Q--;assert(Q>=0);cout<<"? "<<x<<' '<<y<<' '<<z<<endl;cin>>f[Id];return f[Id];}
void Succ(int x,int y,int z){cout<<"! "<<x<<' '<<y<<' '<<z<<endl;exit(0);}
int main(){
cin>>n>>m>>k>>Q;int i,j,h;
if(m==1&&k==1){
int l=1,r=n;while(l+1<r){
int mid=l+r>>1;
if(Qry(l,1,1)>=Qry(mid,1,1)) r=mid;
else if(Qry(r,1,1)>=Qry(mid,1,1)) l=mid;
else if(Qry(mid,1,1)<=Qry(mid+1,1,1)) l=mid;else r=mid;
}
int Mx=0,Id=0;for(int i=l;i<=r;i++) {int p=Qry(i,1,1);p>Mx&&(Mx=p,Id=i);}Succ(Id,1,1);
}
if(k==1){
int l1=1,l2=1,r1=n,r2=m,M1=0,I1=0,M2=0,I2=0,Ix1=0,Ip1=0,Ix2=0,Ip2=0;
while(l1+1<r1){
if(l1+1<r1){
int mid=l1+r1>>1;M1=0,I1=0;for(i=l2;i<=r2;i++) Qry(mid,i,1)>M1&&(M1=Qry(mid,i,1),I1=i);
int p1=Qry(mid+1,I1,1),p2=Qry(mid-1,I1,1);if(M1>=p1&&M1>=p2&&M1>=Qry(mid,I1-1,1)&&M1>=Qry(mid,I1+1,1))Succ(mid,I1,1);
if(M1<Ix2) {
if(Ip2<=mid) r1=mid;else l1=mid;
}
else if(M1<=p1) l1=mid;else r1=mid;
M1>Ix1&&(Ix1=M1,Ip1=I1);
}
if(l2<r2){
int mid=l2+r2>>1;M2=0,I2=0;for(i=l1;i<=r1;i++) Qry(i,mid,1)>M2&&(M2=Qry(i,mid,1),I2=i);
int p1=Qry(I2,mid+1,1),p2=Qry(I2,mid-1,1);if(M2>=p1&&M2>=p2&&M2>=Qry(I2-1,mid,1)&&M2>=Qry(I2+1,mid,1))Succ(I2,mid,1);
if(M2<Ix1){
if(Ip1<=mid) r2=mid;else l2=mid;
}
else if(M2<=p1) l2=mid;else r2=mid;
M2>Ix2&&(Ix2=M2,Ip2=I2);
}
}
int Mx=0;I1=0,I2=0;for(i=l1;i<=r1;i++) for(j=l2;j<=r2;j++) Qry(i,j,1)>Mx&&(Mx=Qry(i,j,1),I1=i,I2=j);Succ(I1,I2,1);
}
int Mx=0,x=0,y=0,z=0;for(i=1;i<=Q/2;i++){
int I1=R(n),I2=R(m),I3=R(k),p=Qry(I1,I2,I3);p>Mx&&(Mx=p,x=I1,y=I2,z=I3);
}while(1){
int p1=Qry(x,y,z+1),p2=Qry(x,y,z-1),p3=Qry(x,y-1,z),p4=Qry(x,y+1,z),p5=Qry(x+1,y,z),p6=Qry(x-1,y,z);
if(Mx>=p1&&Mx>=p2&&Mx>=p3&&Mx>=p4&&Mx>=p5&&Mx>=p6) Succ(x,y,z);
if(Mx<p1) Mx=p1,z++;else if(Mx<p2) Mx=p2,z--;else if(Mx<p3) Mx=p3,y--;
else if(Mx<p4) Mx=p4,y++;else if(Mx<p5) Mx=p5,x++;else Mx=p6,x--;
}
}