This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define ll long long
#define int long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii,int> ipii;
vector <int> vx = {1, -1, 0, 0, 0, 0};
vector <int> vy = {0, 0, 1, -1, 0, 0};
vector <int> vz = {0, 0, 0, 0, 1, -1};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int all, n, m, k, q;
int ansx=-1, ansy, ansz;
map <ipii, int> ma;
int num(int r){
int x = rng(); x = abs(x);
x %= r; x++;
return x;
}
int que(int a, int b, int c){
if(a<=0 || a>n || b<=0 || b>m || c<=0 || c>k) return 0;
if(ma.count(ipii(pii(a, b), c)) != 0) return ma[ipii(pii(a, b), c)];
if(all == q) assert(false);
cout << "? " << a << ' ' << b << ' ' << c << endl;
all++;
int x; cin >> x;
ma[ipii(pii(a, b), c)] = x;
return x;
}
bool aman(int a, int b, int c){
if(a<=0 || a>n || b<=0 || b>m || c<=0 || c>k) return 0;
for(int i=0; i<6; i++){
if(que(a, b, c) < que(a+vx[i], b+vy[i], c+vz[i])) return 0;
}
return 1;
}
signed main(){
cin >> n >> m >> k >> q;
if(m==1 && k==1){
int len = n;
int l=1, r=n, mid1=-1, mid2=-1;
while(r-l+1 >= 4){
len = r-l+1;
if(mid1==-1) mid1 = l+0.382*len;
if(mid2==-1) mid2 = l+0.618*len;
if(mid1 >= mid2){
mid1 = l+0.382*len;
mid2 = l+0.618*len;
if(mid1 >= mid2) break;
}
if(que(mid1, 1, 1) <= que(mid2, 1, 1)){
l = mid1; mid1 = mid2; mid2 = -1;
} else {
r = mid2; mid2 = mid1; mid1 = -1;
}
}
int ans = l;
for(int i=l; i<=r; i++){
if(que(i, 1, 1) >= max(que(i+1, 1, 1), que(i-1, 1, 1))){
ans = i; break;
}
}
// assert(ans != -1);
cout << "! " << ans << " 1 1" << endl;
exit(0);
}
if(m==1){
exit(0);
}
int mx = -1, a=-1, b=-1, c=-1;
for(int i=0; i<q/2; i++){
int x=num(n), y=num(m), z=num(k);
if(mx < que(x,y,z)){
mx=que(x,y,z); a=x; b=y; c=z;
}
}
while(all+6<q){
if(aman(a, b, c)) break;
int mx = -1, x=-1,y=-1,z=-1;
for(int i=0; i<6; i++){
if(mx < que(a+vx[i], b+vy[i], c+vz[i])){
mx=que(a+vx[i], b+vy[i], c+vz[i]);
x=a+vx[i]; y=b+vy[i]; z=c+vz[i];
}
}
}
cout << "! " <<a<<' '<<b<<' '<<c<<endl;
}
Compilation message (stderr)
worm.cpp: In function 'int main()':
worm.cpp:90:16: warning: variable 'x' set but not used [-Wunused-but-set-variable]
90 | int mx = -1, x=-1,y=-1,z=-1;
| ^
worm.cpp:90:21: warning: variable 'y' set but not used [-Wunused-but-set-variable]
90 | int mx = -1, x=-1,y=-1,z=-1;
| ^
worm.cpp:90:26: warning: variable 'z' set but not used [-Wunused-but-set-variable]
90 | int mx = -1, x=-1,y=-1,z=-1;
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |