#include <bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
typedef long long ll;
typedef long double ld;
int n, m, k, q;
map<ll, int> pamiec;
vector<pair<int,pii>> roza = {{0,{0,1}},{0,{0,-1}},{0,{1,0}},{0,{-1,0}},{1,{0,0}},{-1,{0,0}}};
int pars(int x, int y, int z){
if(x < 1 or x > n or y < 1 or y > m or z < 1 or z > k) return 0;
ll G = x - 1 + (y-1) * n + (z-1) *n*m;
if(pamiec.find(G) != pamiec.end()) return pamiec[G];
cout << "? " << x << " " << y << " " << z << "\n";
cin >> pamiec[G];
return pamiec[G];
}
pair<int, pii> synowie(int x, int y, int z){
int curr = pars(x, y, z);
for(auto u : roza){
int x2 = x + u.first;
int y2 = y + u.second.first;
int z2 = z + u.second.second;
if(pars(x2,y2,z2) > curr) return {x2, {y2,z2}};
}
return {-1, {-1, -1}};
}
int znajdz1d(int a, int b, pii znane){
if(a > b) return -1;
if(a == b) return a;
if(b - a + 1 <= 5){
for(int i = a; i <= b; ++i){
int lewo = pars(i-1, 1, 1);
int curr = pars(i, 1, 1);
int prawo = pars(i+1, 1, 1);
if(curr >= lewo and curr >= prawo){
return i;
}
}
}
pii split = znane;
if(split.first == -1){
split.first = (0.618 * (ld)a + 0.382 * (ld)b);
}
if(split.second == -1){
split.second = ((ld)0.382 * (ld)a + (ld)0.618 * (ld)b);
}
if(split.first <= a){
split.first = a + 1;
}
if(split.second >= b){
split.second = b-1;
}
if(split.first == split.second){
if(split.second + 1 != b) split.second++;
else split.first--;
}
if(split.first >= split.second) swap(split.first, split.second);
int L1 = pars(split.first, 1, 1);
int L2 = pars(split.second, 1, 1);
// cout << a << " " << b << " ab\n";
// cout << split.first << " " << split.second << " spl\n";
// cout << L1 << " " << L2 << " L\n";
if(L1 >= L2){
return znajdz1d(a, split.second - 1, {-1, split.first});
}
else{
return znajdz1d(split.first + 1, b, {split.second, -1});
}
// if(a == b) return a;
// if(b - a + 1 <= 3){
// for(int i = a; i <= b; ++i){
// int lewo = pars(i-1, 1, 1);
// int curr = pars(i, 1, 1);
// int prawo = pars(i+1, 1, 1);
// if(curr >= lewo and curr >= prawo){
// return i;
// }
// }
// }
// ll mid = (a + b) / 2;
// ll nxt = mid + 1;
// int L1 = pars(mid, 1, 1);
// int L2 = pars(nxt, 1, 1);
// if(L1 >= L2){
// return znajdz1d(a, mid, {-1,-1});
// }
// else{
// return znajdz1d(nxt, b, {-1, -1});
// }
}
bool spr(pii x){
int i = x.first;
int j = x.second;
int lew = pars(i,j-1,1);
int gor = pars(i+1,j,1);
int pra = pars(i,j+1,1);
int dol = pars(i-1,j,1);
int mid = pars(i,j,1);
if(mid >= lew and mid >= pra and mid >= gor and mid >= dol) return true;
return false;
}
pii znajdz2d(pii lewydolny, pii prawygorny, int prevmax, pii prevwhere, int kierunek){
if(abs(lewydolny.first - prawygorny.first) * abs(lewydolny.second - prawygorny.second) <= 50){
for(int i = lewydolny.first; i <= prawygorny.first; ++i){
for(int j = lewydolny.second; j <= prawygorny.second; ++j){
if(spr({i,j})) return {i, j};
}
}
return {-1, -1};
}
if(kierunek == 0){
int mid = (lewydolny.second + prawygorny.second) / 2;
int mx = -1;
pii where;
for(int i = lewydolny.first; i <= prawygorny.first; ++i){
int T = pars(i, mid, 1);
if(T >= mx){
mx = T;
where = {i, mid};
}
}
if(spr(where)) return where;
int L1 = pars(where.first, where.second - 1, 1);
int L2 = pars(where.first, where.second + 1, 1);
if(max(L1, L2) >= prevmax){
if(L1 >= L2){
return znajdz2d(lewydolny, {prawygorny.first, mid - 1}, L1, {where.first - 1, where.second}, kierunek ^ 1);
}
else{
return znajdz2d({lewydolny.first, mid + 1}, prawygorny, L2, {where.first + 1, where.second}, kierunek ^ 1);
}
}
else{
if(prevwhere.second > mid){
return znajdz2d({lewydolny.first, mid + 1}, prawygorny, prevmax, prevwhere, kierunek ^ 1);
}
else{
return znajdz2d(lewydolny, {prawygorny.first, mid - 1}, prevmax, prevwhere, kierunek ^ 1);
}
}
}
else{
int mid = (lewydolny.first + prawygorny.first) / 2;
int mx = -1;
pii where;
for(int j = lewydolny.second; j <= prawygorny.second; ++j){
int T = pars(mid, j, 1);
if(T > mx){
mx = T;
where = {mid, j};
}
}
if(spr(where)) return where;
int L1 = pars(where.first - 1, where.second, 1);
int L2 = pars(where.first + 1, where.second, 1);
if(max(L1, L2) >= prevmax){
if(L1 >= L2){
return znajdz2d(lewydolny, {mid - 1, prawygorny.second}, L1, {where.first - 1, where.second}, kierunek ^ 1);
}
else{
return znajdz2d({mid + 1, lewydolny.second}, prawygorny, L2, {where.first + 1, where.second}, kierunek ^ 1);
}
}
else{
if(prevwhere.first > mid){
return znajdz2d({mid + 1, lewydolny.second}, prawygorny, prevmax, prevwhere, kierunek ^ 1);
}
else{
return znajdz2d(lewydolny, {mid - 1, prawygorny.second}, prevmax, prevwhere, kierunek ^ 1);
}
}
}
}
int main(){
cin >> n >> m >> k >> q;
if(m == 1 and k == 1 and q <= 35){
int x = znajdz1d(1, n, {-1, -1});
cout << "! " << x << " " << 1 << " " << 1 << "\n";
}
else if(k == 1 and q <= 3500){
pii X = znajdz2d({1, 1}, {n, n}, 0, {-1, -1}, 0);
cout << "! " << X.first << " " << X.second << " " << 1 << "\n";
}
else{
srand(time(NULL));
pair<int,pair<int,pii>> naj = {-1, {-1, {-1, -1}}};
for(int i = 0; i < q/3; ++i){
int x = rand() % n + 1;
int y = rand() % m + 1;
int z = rand() % k + 1;
naj = max(naj, {pars(x,y,z), {x, {y, z}}});
}
int x = naj.second.first;
int y = naj.second.second.first;
int z = naj.second.second.second;
while(true){
pair<int,pii> nxt = synowie(x, y, z);
if(nxt.first == -1) break;
x = nxt.first;
y = nxt.second.first;
z = nxt.second.second;
}
cout << "! " << x << " " << y << " " << z << "\n";
}
return 0;
}
# | 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... |