oj.uz

Submission #250929

# Submission time Handle Problem Language Result Execution time Memory
250929 2020-07-19T13:14:20 Z imeimi2000 Worm Worries (BOI18_worm) C++17
100 / 100
 974 ms 5752 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>
 
using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;
 
int n, m, k, q, a;
int ask(int x = 1, int y = 1, int z = 1) {
    static map<llong, int> mp;
    if (x <= 0) return 0;
    if (y <= 0) return 0;
    if (z <= 0) return 0;
    if (x > n) return 0;
    if (y > m) return 0;
    if (z > k) return 0;
    llong v = x + y * (n + 5ll) + z * (n + 5ll) * (m + 5ll);
    if (mp.find(v) != mp.end()) return mp[v];
    if (q < ++a) exit(1);
    int r;
    printf("? %d %d %d\n", x, y, z);
    fflush(stdout);
    scanf("%d", &r);
    return mp[v] = r;
}
 
void answer(int x = 1, int y = 1, int z = 1) {
    printf("! %d %d %d\n", x, y, z);
    exit(0);
}
 
int gox[6] = { 1, -1, 0, 0, 0, 0 };
int goy[6] = { 0, 0, 1, -1, 0, 0 };
int goz[6] = { 0, 0, 0, 0, 1, -1 };
 
int checkLocalMin(int x = 1, int y = 1, int z = 1) {
    for (int i = 0; i < 6; ++i) {
        if (ask(x, y, z) < ask(x + gox[i], y + goy[i], z + goz[i])) return 0;
    }
    return 1;
}
 
int main() {
    scanf("%d%d%d%d", &n, &m, &k, &q);
	if (k > 1) {
        srand(time(0));
        int x = (n + 1) / 2;
        int y = (m + 1) / 2;
        int z = (k + 1) / 2;
        int it = q / 2;
        while (it--) {
            int mx = rand() % n + 1;
            int my = rand() % m + 1;
            int mz = rand() % k + 1;
            if (ask(x, y, z) < ask(mx, my, mz)) x = mx, y = my, z = mz;
        }
        while (1) {
            vector<int> ch = { 0, 1, 2, 3, 4, 5 };
            random_shuffle(ch.begin(), ch.end());
            int c = 0;
            for (int i : ch) {
                if (ask(x, y, z) < ask(x + gox[i], y + goy[i], z + goz[i])) {
                    x += gox[i];
                    y += goy[i];
                    z += goz[i];
                    c = 1;
                    break;
                }
            }
            if (c) continue;
            answer(x, y, z);
        }
	}
	else if (m > 1) {
        int sx = 1, ex = n;
        int sy = 1, ey = m;
        int mx = 0, my = 0, mv = 0;
        while (sx < ex || sy < ey) {
            if (ex - sx < ey - sy) {
                int md = (sy + ey) / 2;
                if (md == my) ++md;
                int mxv = 0, mxi = 0;
                for (int i = sx; i <= ex; ++i) {
                    if (mxv < ask(i, md)) mxv = ask(i, md), mxi = i;
                }
                if (mv < mxv) {
                    int l = ask(mxi, md - 1);
                    int r = ask(mxi, md + 1);
                    if (l <= mxv && r <= mxv) answer(mxi, md);
                    mx = mxi;
                    if (l > r) ey = max(md - 1, sy), my = md - 1, mv = l;
                    else sy = min(md + 1, ey), my = md + 1, mv = r;
                }
                else {
                    if (my < md) ey = max(md - 1, sy);
                    else sy = min(md + 1, ey);
                }
            }
            else {
                int md = (sx + ex) / 2;
                if (md == mx) ++md;
                int mxv = 0, mxi = 0;
                for (int i = sy; i <= ey; ++i) {
                    if (mxv < ask(md, i)) mxv = ask(md, i), mxi = i;
                }
                if (mv < mxv) {
                    int l = ask(md - 1, mxi);
                    int r = ask(md + 1, mxi);
                    if (l <= mxv && r <= mxv) answer(md, mxi);
                    my = mxi;
                    if (l > r) ex = max(md - 1, sx), mx = md - 1, mv = l;
                    else sx = min(md + 1, ex), mx = md + 1, mv = r;
                }
                else {
                    if (mx < md) ex = max(md - 1, sx);
                    else sx = min(md + 1, ex);
                }
            }
        }
        answer(mx, my);
	}
	else {
        int s = 1, e = n;
        const double p = 0.382;
        int l = (1 - p) * s + p * e;
        int r = s + e - l;
        while (s < e) {
            if (ask(l) < ask(r)) s = l + 1, l = r, r = max(p * s + (1 - p) * e, l + 1.0);
            else e = r - 1, r = l, l = min((1 - p) * s + p * e, r - 1.0);
        }
        answer(s);
	}
	return 0;
}

Compilation message

worm.cpp: In function 'int ask(int, int, int)':
worm.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &r);
     ~~~~~^~~~~~~~~~
worm.cpp: In function 'int main()':
worm.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d", &n, &m, &k, &q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 0 ms 256 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 0 ms 256 KB Output is correct
9 Correct 0 ms 256 KB Output is correct
10 Correct 0 ms 256 KB Output is correct
11 Correct 0 ms 256 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 7 ms 384 KB Output is correct
5 Correct 7 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 384 KB Output is correct
2 Correct 25 ms 504 KB Output is correct
3 Correct 9 ms 384 KB Output is correct
4 Correct 27 ms 504 KB Output is correct
5 Correct 29 ms 504 KB Output is correct
6 Correct 28 ms 544 KB Output is correct
7 Correct 26 ms 632 KB Output is correct
8 Correct 25 ms 504 KB Output is correct
9 Correct 26 ms 504 KB Output is correct
10 Correct 23 ms 504 KB Output is correct
11 Correct 29 ms 504 KB Output is correct
12 Correct 15 ms 500 KB Output is correct
13 Correct 16 ms 516 KB Output is correct
14 Correct 28 ms 504 KB Output is correct
15 Correct 28 ms 632 KB Output is correct
16 Correct 32 ms 504 KB Output is correct
17 Correct 27 ms 504 KB Output is correct
18 Correct 30 ms 632 KB Output is correct
19 Correct 30 ms 504 KB Output is correct
20 Correct 18 ms 384 KB Output is correct
21 Correct 32 ms 628 KB Output is correct
22 Correct 26 ms 504 KB Output is correct
23 Correct 29 ms 504 KB Output is correct
24 Correct 28 ms 504 KB Output is correct
25 Correct 27 ms 504 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 435 ms 3504 KB Output is correct
2 Correct 433 ms 3332 KB Output is correct
3 Correct 471 ms 3400 KB Output is correct
4 Correct 424 ms 3576 KB Output is correct
5 Correct 525 ms 3452 KB Output is correct
6 Correct 422 ms 3424 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 673 ms 5144 KB Output is correct
2 Correct 750 ms 5112 KB Output is correct
3 Correct 807 ms 5016 KB Output is correct
4 Correct 730 ms 5752 KB Output is correct
5 Correct 974 ms 5628 KB Output is correct
6 Correct 675 ms 5500 KB Output is correct
7 Correct 657 ms 5252 KB Output is correct
8 Correct 794 ms 5524 KB Output is correct
9 Correct 723 ms 5736 KB Output is correct
10 Correct 746 ms 5496 KB Output is correct
11 Correct 699 ms 5108 KB Output is correct