oj.uz

Submission #757088

# Submission time Handle Problem Language Result Execution time Memory
757088 2023-06-12T14:50:43 Z maomao90 Worm Worries (BOI18_worm) C++17
100 / 100
 931 ms 232644 KB 
// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h> 
using namespace std;

#define REP(i, s, e) for (int i = (s); i < (e); i++)
#define RREP(i, s, e) for (int i = (s); i >= (e); i--)
template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define SZ(_a) (int) _a.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<iii> viii;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

const int INF = 1000000005;
const ll LINF = 1000000000000000005ll;
const int MAXN = 1000005;

int query(int x, int y, int z) {
    cout << "? " << x << ' ' << y << ' ' << z << endl;
	int ans; cin >> ans;
	if (ans == -1) exit(0);
	return ans;
}

void guess(int x, int y, int z) {
    cout << "! " << x << ' ' << y << ' ' << z << endl;
	exit(0);
}

int n, m, k, q;

namespace st2 {
    const int MAXN = 1000005;
    int qry[MAXN];
    int fib[MAXN];
    int query(int x, int y, int z) {
        if (x > n) {
            return 0;
        }
        if (qry[x]) {
            return qry[x];
        }
        cout << "? " << x << ' ' << y << ' ' << z << endl;
        int ans; cin >> ans;
        if (ans == -1) exit(0);
        return qry[x] = ans;
    }
    int main() {
        fib[0] = 1; fib[1] = 2;
        int gd = -1;
        REP (i, 2, 50) {
            fib[i] = fib[i - 1] + fib[i - 2];
            if (fib[i] + 1 >= n) {
                gd = i;
                break;
            }
        }
        int lo = 1, hi = fib[gd] + 1;
        int ans = -1;
        RREP (k, gd, 2) {
            int mid1 = lo + fib[k - 2], mid2 = lo + fib[k - 1];
            assert(hi == lo + fib[k]);
            cerr << ' ' << mid1 << ' ' << mid2 << '\n';
            int l = query(mid1, 1, 1), r = query(mid2, 1, 1);
            if (l > r) {
                hi = mid2;
            } else {
                lo = mid1;
            }
        }
        assert(lo + 2 == hi);
        int l = query(lo, 1, 1), m = query(lo + 1, 1, 1), r = query(hi, 1, 1);
        if (l >= m) {
            guess(lo, 1, 1);
        } else if (m >= l && m >= r) {
            guess(lo + 1, 1, 1);
        } else {
            assert(r >= m);
            guess(hi, 1, 1);
        }
        /*
        int lo = 1, hi = n;
        while (lo < hi) {
            int mid = lo + hi + 1 >> 1;
            int l = query(mid - 1, 1, 1), m = query(mid, 1, 1);
            if (l < m) {
                lo = mid;
            } else {
                hi = mid - 1;
            }
        }
        guess(lo, 1, 1);
        */
        return 0;
    }
}

namespace st4 {
    const int MAXN = 1005;
    int qry[MAXN][MAXN];
    int query(int x, int y, int z = 1) {
        if (x > n || y > m || x <= 0 || y <= 0) {
            return 0;
        }
        if (qry[x][y]) {
            return qry[x][y];
        }
        cout << "? " << x << ' ' << y << ' ' << z << endl;
        int ans; cin >> ans;
        if (ans == -1) exit(0);
        return qry[x][y] = ans;
    }
    bool solve(int mnx, int mxx, int mny, int mxy, iii mx) {
        cerr << mnx << ' ' << mxx << ' ' << mny << ' ' << mxy << ' ' << get<0>(mx) << ' ' << get<1>(mx) << ' ' << get<2>(mx) << '\n';
        if (mxx - mnx >= mxy - mny) {
            int mid = mnx + mxx >> 1;
            ii tmx = {-1, -1};
            REP (i, mny, mxy + 1) {
                mxto(tmx, {query(mid, i), i});
            }
            if (get<0>(mx) > tmx.FI) {
                if (get<1>(mx) <= mid) {
                    return solve(mnx, mid - 1, mny, mxy, mx);
                } else {
                    return solve(mid + 1, mxx, mny, mxy, mx);
                }
            } else {
                int up = query(mid + 1, tmx.SE), bt = query(mid - 1, tmx.SE);
                if (up > tmx.FI) {
                    return solve(mid + 1, mxx, mny, mxy, {up, mid + 1, tmx.SE});
                } else if (bt > tmx.FI) {
                    return solve(mnx, mid - 1, mny, mxy, {bt, mid - 1, tmx.SE});
                } else {
                    guess(mid, tmx.SE, 1);
                    return 1;
                }
            }
        }
        int mid = mny + mxy >> 1;
        ii tmx = {-1, -1};
        REP (i, mnx, mxx + 1) {
            mxto(tmx, {query(i, mid), i});
        }
        if (get<0>(mx) > tmx.FI) {
            if (get<2>(mx) <= mid) {
                return solve(mnx, mxx, mny, mid - 1, mx);
            } else {
                return solve(mnx, mxx, mid + 1, mxy, mx);
            }
        } else {
            int up = query(tmx.SE, mid + 1), bt = query(tmx.SE, mid - 1);
            if (up > tmx.FI) {
                return solve(mnx, mxx, mid + 1, mxy, {up, tmx.SE, mid + 1});
            } else if (bt > tmx.FI) {
                return solve(mnx, mxx, mny, mid - 1, {bt, tmx.SE, mid - 1});
            } else {
                guess(tmx.SE, mid, 1);
                return 1;
            }
        }
    }
    int main() {
        assert(solve(1, n, 1, m, {-1, -1, -1}));
        return 0;
    }
}

namespace st6 {
    const int MAXN = 505;
    const int dirx[] = {1, -1, 0, 0, 0, 0}, diry[] = {0, 0, 1, -1, 0, 0}, dirz[] = {0, 0, 0, 0, 1, -1};
    mt19937 rnd(8);
    int qry[MAXN][MAXN][MAXN];
    int query(int x, int y, int z) {
        if (x > n || y > m || z > k || x <= 0 || y <= 0 || z <= 0) {
            return 0;
        }
        if (qry[x][y][z]) {
            return qry[x][y][z];
        }
        cout << "? " << x << ' ' << y << ' ' << z << endl;
        int ans; cin >> ans;
        if (ans == -1) exit(0);
        return qry[x][y][z] = ans;
    }
    int main() {
        int mx = -1, sx, sy, sz;
        REP (_, 0, q / 2) {
            int x = rnd() % n + 1, y = rnd() % m + 1, z = rnd() % k + 1;
            if (mxto(mx, query(x, y, z))) {
                sx = x; sy = y; sz = z;
            }
        }
        while (1) {
            bool fnd = 0;
            REP (d, 0, 6) {
                int nx = sx + dirx[d], ny = sy + diry[d], nz = sz + dirz[d];
                int nmx = query(nx, ny, nz);
                if (nmx > mx) {
                    fnd = 1;
                    sx = nx, sy = ny, sz = nz;
                    mx = nmx;
                    break;
                }
            }
            if (!fnd) {
                guess(sx, sy, sz);
                return 0;
            }
        }
        assert(0);
    }
}

int main() {
    cin >> n >> m >> k >> q;
    if (m == 1 && k == 1) {
        st2::main();
    } else if (k == 1) {
        st4::main();
    } else {
        st6::main();
    }
}

Compilation message

worm.cpp: In function 'int st2::main()':
worm.cpp:79:13: warning: unused variable 'ans' [-Wunused-variable]
   79 |         int ans = -1;
      |             ^~~
worm.cpp: In function 'bool st4::solve(int, int, int, int, iii)':
worm.cpp:136:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  136 |             int mid = mnx + mxx >> 1;
      |                       ~~~~^~~~~
worm.cpp:159:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  159 |         int mid = mny + mxy >> 1;
      |                   ~~~~^~~~~
worm.cpp: In function 'int st6::main()':
worm.cpp:226:22: warning: 'sz' may be used uninitialized in this function [-Wmaybe-uninitialized]
  226 |                 guess(sx, sy, sz);
      |                 ~~~~~^~~~~~~~~~~~
worm.cpp:226:22: warning: 'sy' may be used uninitialized in this function [-Wmaybe-uninitialized]
worm.cpp:226:22: warning: 'sx' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1
10.0 / 10.0

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

Subtask #2
22.0 / 22.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 328 KB Output is correct
2 Correct 4 ms 700 KB Output is correct
3 Correct 3 ms 208 KB Output is correct
4 Correct 10 ms 688 KB Output is correct
5 Correct 8 ms 712 KB Output is correct
6 Correct 4 ms 592 KB Output is correct
7 Correct 5 ms 592 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 332 KB Output is correct
2 Correct 33 ms 2220 KB Output is correct
3 Correct 13 ms 324 KB Output is correct
4 Correct 29 ms 2236 KB Output is correct
5 Correct 33 ms 2248 KB Output is correct
6 Correct 28 ms 2232 KB Output is correct
7 Correct 33 ms 2248 KB Output is correct
8 Correct 33 ms 2240 KB Output is correct
9 Correct 28 ms 2232 KB Output is correct
10 Correct 27 ms 2180 KB Output is correct
11 Correct 32 ms 2232 KB Output is correct
12 Correct 37 ms 2248 KB Output is correct
13 Correct 27 ms 2200 KB Output is correct
14 Correct 29 ms 2280 KB Output is correct
15 Correct 32 ms 2276 KB Output is correct
16 Correct 31 ms 2236 KB Output is correct
17 Correct 48 ms 2228 KB Output is correct
18 Correct 32 ms 2188 KB Output is correct
19 Correct 32 ms 2248 KB Output is correct
20 Correct 23 ms 2204 KB Output is correct
21 Correct 29 ms 2248 KB Output is correct
22 Correct 29 ms 2244 KB Output is correct
23 Correct 29 ms 2244 KB Output is correct
24 Correct 28 ms 2276 KB Output is correct
25 Correct 32 ms 2232 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 536 ms 20496 KB Output is correct
2 Correct 474 ms 20520 KB Output is correct
3 Correct 436 ms 20692 KB Output is correct
4 Correct 415 ms 20688 KB Output is correct
5 Correct 502 ms 20416 KB Output is correct
6 Correct 388 ms 20612 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 822 ms 226176 KB Output is correct
2 Correct 762 ms 226032 KB Output is correct
3 Correct 817 ms 225888 KB Output is correct
4 Correct 872 ms 226024 KB Output is correct
5 Correct 856 ms 230544 KB Output is correct
6 Correct 856 ms 225888 KB Output is correct
7 Correct 810 ms 226696 KB Output is correct
8 Correct 691 ms 229424 KB Output is correct
9 Correct 931 ms 232644 KB Output is correct
10 Correct 699 ms 226956 KB Output is correct
11 Correct 747 ms 228024 KB Output is correct