이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
const double PHI = 1.61803398874;
struct Coords {
int x,y,z;
};
int ask(vvvi & H, int x, int y, int z) {
if (x == 0 || x == H.size()-1 ||
y == 0 || y == H[0].size()-1 ||
z == 0 || z == H[0][0].size()-1) return 0;
// int A[8][7] = {
// { 37, 36, 35, 34, 33, 32, 31 } ,
// { 1, 1, 1, 1, 1, 1, 30 },
// { 13, 12, 11, 10, 9, 1, 29 },
// { 14, 1, 1, 1, 8, 1, 28 },
// { 15, 1, 3, 1, 7, 1, 27 },
// { 16, 1, 4, 5, 6, 1, 26 },
// { 17, 1, 1, 1, 1, 1, 25 },
// { 18, 19, 20, 21, 22, 23, 24 }
// };
if (H[x][y][z] == -1) {
printf("? %d %d %d\n", x, y, z);
fflush(stdout);
scanf("%d", &H[x][y][z]);
// H[x][y][z] = A[y-1][x-1];
}
return H[x][y][z];
}
int ask(vvvi & H, Coords c) { return ask(H, c.x, c.y, c.z); }
Coords null = { -1, -1, -1 };
Coords getBetter(vvvi & H, int x, int y, int z) {
int mValue = ask(H, x, y, z);
Coords alt;
vector<Coords> neighbors = {
{ x+1, y, z },
{ x-1, y, z },
{ x, y+1, z },
{ x, y-1, z },
{ x, y, z+1 },
{ x, y, z-1 }
};
for (Coords n : neighbors) {
if (ask(H, n) > mValue) {
mValue = ask(H, n);
alt = n;
}
}
if (mValue == ask(H, x, y, z)) return null;
else return alt;
}
Coords getBetter(vvvi & H, Coords c) { return getBetter(H, c.x, c.y, c.z); }
int random(int n, mt19937 & rng) {
return ((int) rng() % n + n) % n;
}
int main() {
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int N, M, K, Q;
scanf("%d %d %d %d", &N, &M, &K, &Q);
vvvi H(N+2, vvi(M+2, vi(K+2, -1)));
if (K != 1) {
Coords maxi = { 1, 1, 1 };
int x, y, z;
for (int i = 0; i < Q / 2; ++i) {
x = random(N, rng) + 1;
y = random(M, rng) + 1;
z = random(K, rng) + 1;
if (ask(H, x, y, z) > ask(H, maxi)) maxi = { x, y, z };
}
while (getBetter(H, maxi).x != -1) maxi = getBetter(H, maxi);
printf("! %d %d %d", maxi.x, maxi.y, maxi.z);
} else if (M != 1) {
Coords maxi = { N, M, K };
Coords tl = { 1, 1, 1};
Coords br = { N, M, K };
bool vert = false;
while (getBetter(H, maxi).x != -1) {
Coords maxv = { 0, 0, 0 };
int xw = (tl.x + br.x) / 2;
int yw = (tl.y + br.y) / 2;
int zw = (tl.z + br.z) / 2;
if (vert) {
for (yw = tl.y; yw <= br.y; ++yw) {
if (ask(H, xw, yw, zw) > ask(H, maxv)) maxv = { xw, yw, zw };
}
} else {
for (xw = tl.x; xw <= br.x; ++xw) {
if (ask(H, xw, yw, zw) > ask(H, maxv)) maxv = { xw, yw, zw };
}
}
if (getBetter(H, maxv).x == -1) { maxi = maxv; break; }
else { maxv = getBetter(H, maxv); }
if (ask(H, maxv) > ask(H, maxi)) maxi = maxv;
if (vert) {
if (maxi.x > xw) tl.x = xw+1;
else br.x = xw-1;
} else {
if (maxi.y > yw) tl.y = yw+1;
else br.y = yw-1;
}
vert = !vert;
}
printf("! %d %d %d", maxi.x, maxi.y, maxi.z);
} else {
int l = 0, r = N + 1, m = 1 / PHI * (r - l);
while (r - l > 2) {
bool right = (r - m > m - l);
int mm;
if (right) { // rechts ist größer...
mm = ceil(r - 1.0 / PHI * (r - m));
if (ask(H, mm, 1, 1) >= ask(H, m, 1, 1)) {
l = m;
m = mm;
} else {
r = mm;
}
} else {
mm = floor(l + 1 / PHI * (m - l));
if (ask(H, mm, 1, 1) >= ask(H, m, 1, 1)) {
r = m;
m = mm;
} else {
l = mm;
}
}
}
printf("! %d %d %d\n", m, 1, 1);
}
fflush(stdout);
}
컴파일 시 표준 에러 (stderr) 메시지
worm.cpp: In function 'int ask(std::vector<std::vector<std::vector<int> > >&, int, int, int)':
worm.cpp:15:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::vector<int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
15 | if (x == 0 || x == H.size()-1 ||
| ~~^~~~~~~~~~~~~
worm.cpp:16:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
16 | y == 0 || y == H[0].size()-1 ||
| ~~^~~~~~~~~~~~~~~~
worm.cpp:17:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | z == 0 || z == H[0][0].size()-1) return 0;
| ~~^~~~~~~~~~~~~~~~~~~
worm.cpp:31:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
31 | scanf("%d", &H[x][y][z]);
| ~~~~~^~~~~~~~~~~~~~~~~~~
worm.cpp: In function 'int main()':
worm.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
69 | scanf("%d %d %d %d", &N, &M, &K, &Q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |