oj.uz

Submission #651105

# Submission time Handle Problem Language Result Execution time Memory
651105 2022-10-17T06:48:18 Z fatemetmhr Worm Worries (BOI18_worm) C++17
100 / 100
 800 ms 31856 KB 
// ~ Be Name Khoda ~

// Harf ke nazanim... 
// Zende bemoonim?
// Ya oonm na?


#include<bits/stdc++.h>

using namespace std;
mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());

typedef long long   ll;
typedef long double ld;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  1e6   + 10;
const int maxn5 =  5e5   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   +  7;
const ld  grt   =  (1 + sqrt(5)) / (2.0);
const ll  inf   =  1e18;


 
int n, m, k, q;
map <pair<int, int>, ll> av[maxn5];
pair<int, int> nei[6] = {mp(0, 1), mp(0, -1), mp(1, 0), mp(-1, 0), mp(0, 0), mp(0, 0)};
ll ans[7];
int mxx = -1, mxy, mxz;
 
 
inline ll ask(int x, int y = 1, int z = 1){
    if(x < 1 || x > n || y < 1 || y > m || z < 1 || z > k)
        return -1;
    if(av[z].find({x, y}) != av[z].end())
        return av[z][{x, y}];
    cout << "? " << x << ' ' << y << ' ' << z << endl;
    cin >> av[z][{x, y}];
    if(mxx == -1 || av[mxz][mp(mxx, mxy)] < av[z][mp(x, y)])
        mxx = x, mxy = y, mxz = z;
    if(av[z][{x, y}] == -1)
        exit(0);
    return av[z][{x, y}];
}

inline void solve1d(){
    int l = 1, r = n;
    if(ask(l) >= ask(l + 1)){
        cout << "! " << 1 << ' ' << 1 << ' ' << 1 << endl;
        return;
    }
    if(ask(r) >= ask(r - 1)){
        cout << "! " << n << ' ' << 1 << ' ' << 1 << endl;
        return;
    }
    int x2 = n / grt + 1, x1 = n - n / grt;
    while(r - l + 1 >= 3){
        if(x1 == l || x2 == r || x1 >= x2)
            break;
        if(ask(x1) < ask(x2)){
            l = x1;
            x1 = x2;
            x2 = l + (r - l + 1) / grt;
        }
        else{
            r = x2;
            x2 = x1;
            x1 = r - (r - l + 1) / grt;
        }
    }

    int mx = l + 1;
    for(int i = l + 2; i < r; i++) if(ask(i) > ask(mx))
        mx = i;
    cout << "! " << mx << ' ' << 1 << ' ' << 1 << endl;
    return;
}

inline void solve2d(){
    int xl = 1, xr = n, yl = 1, yr = m;
    int mxx = 1, mxy = 1;
    while(xl < xr || yl < yr){
        if(xr - xl < yr - yl){
            int mid = (yl + yr) >> 1, mx = xl;
            for(int i = xl + 1; i <= xr; i++) 
                if(ask(i, mid) > ask(mx, mid))
                    mx = i;
            int bnei = 5;
            ans[5] = ask(mx, mid);
            for(int i = 0; i < 4; i++){
                ans[i] = ask(mx + nei[i].fi, mid + nei[i].se);
                if(ans[i] > ans[bnei]){
                    bnei = i;
                }
            }
            if(bnei == 5){
                cout << "! " << mx << ' ' << mid << ' ' << 1 << endl;
                return;
            }
            int xb = mx + nei[bnei].fi, yb = mid + nei[bnei].se;
            if(yb == mid || ask(xb, yb) < ask(mxx, mxy)){
                if(mxy < mid)
                    yr = mid - 1;
                else
                    yl = mid + 1;
            }
            else{
                if(yb < mid)
                    yr = mid - 1;
                else
                    yl = mid + 1;
                mxx = xb; mxy = yb;
            }
        }
        else{
            int mid = (xl + xr) >> 1, mx = yl;
            for(int i = yl + 1; i <= yr; i++) 
                if(ask(mid, i) > ask(mid, mx))
                    mx = i;
            int bnei = 5;
            ans[5] = ask(mid, mx);
            for(int i = 0; i < 4; i++){
                ans[i] = ask(mid + nei[i].fi, mx + nei[i].se);
                if(ans[i] > ans[bnei]){
                    bnei = i;
                }
            }
            if(bnei == 5){
                cout << "! " << mid << ' ' << mx << ' '<< 1 << endl;
                return;
            }
            int xb = mid + nei[bnei].fi, yb = mx + nei[bnei].se;
            if(xb == mid || ask(xb, yb) < ask(mxx, mxy)){
                if(mxx < mid)
                    xr = mid - 1;
                else
                    xl = mid + 1;
            }
            else{
                if(xb < mid)
                    xr = mid - 1;
                else
                    xl = mid + 1;
                mxx = xb; mxy = yb;
            }
        }
    }
    cout << "! " << xl << ' ' << yl << ' ' << 1 << endl;
    return;
}

inline void solve3d(){
    int tt = 30000;
    while(tt--){
        int x = rng() % n + 1, y = rng() % m + 1, z = rng() % k + 1;
        if(av[z].find({x, y}) != av[z].end()){
            tt++;
            continue;
        }
        ask(x, y, z);
    }

    int x = mxx, y = mxy, z = mxz;
    while(true){
        int mx = 6; ans[6] = av[z][mp(x, y)];
        for(int i = 0; i < 6; i++){
            ans[i] = ask(x + nei[i].fi, y + nei[i].se, z + (i == 4 ? 1 : (i == 5 ? -1 : 0)));
            if(ans[i] > ans[mx]){
                mx = i;
                break;
            }
        }
        if(mx == 6){
            cout << "! " << x << ' ' << y << ' ' << z << endl;
            return;
        }
        x += nei[mx].fi;
        y += nei[mx].se;
        z += (mx == 4 ? 1 : (mx == 5 ? -1 : 0));
    }
    return;
}
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    cin >> n >> m >> k >> q;

    if(m == 1)
        solve1d();
    else if(k == 1)
        solve2d();
    else
        solve3d();
}

/*
5610 6793 6641 2049 2223 1965 2184 4610 6411 3212 
255  4906 6242 3562 8231 8399 7118 8195 8224 1593 
4500 9240 7705 7709 5735 4886 7327 4052 1976 3103 
653  6416 7165 5924 2822 5975 9607 8960 217  1287 
2051 4176 9826 3025 983  4140 1416 8184 8580 3233
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23760 KB Output is correct
2 Correct 14 ms 23732 KB Output is correct
3 Correct 11 ms 23760 KB Output is correct
4 Correct 12 ms 23760 KB Output is correct
5 Correct 13 ms 23760 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23760 KB Output is correct
2 Correct 11 ms 23760 KB Output is correct
3 Correct 11 ms 23760 KB Output is correct
4 Correct 12 ms 23768 KB Output is correct
5 Correct 12 ms 23760 KB Output is correct
6 Correct 11 ms 23760 KB Output is correct
7 Correct 12 ms 23760 KB Output is correct
8 Correct 13 ms 23760 KB Output is correct
9 Correct 12 ms 23684 KB Output is correct
10 Correct 11 ms 23760 KB Output is correct
11 Correct 11 ms 23760 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23760 KB Output is correct
2 Correct 17 ms 23824 KB Output is correct
3 Correct 13 ms 23760 KB Output is correct
4 Correct 20 ms 23724 KB Output is correct
5 Correct 17 ms 23836 KB Output is correct
6 Correct 17 ms 23764 KB Output is correct
7 Correct 18 ms 23760 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23848 KB Output is correct
2 Correct 38 ms 23852 KB Output is correct
3 Correct 22 ms 23808 KB Output is correct
4 Correct 41 ms 23880 KB Output is correct
5 Correct 38 ms 23956 KB Output is correct
6 Correct 40 ms 23944 KB Output is correct
7 Correct 44 ms 23968 KB Output is correct
8 Correct 47 ms 23972 KB Output is correct
9 Correct 41 ms 23912 KB Output is correct
10 Correct 41 ms 23964 KB Output is correct
11 Correct 41 ms 23860 KB Output is correct
12 Correct 41 ms 23948 KB Output is correct
13 Correct 42 ms 23948 KB Output is correct
14 Correct 46 ms 23968 KB Output is correct
15 Correct 46 ms 23968 KB Output is correct
16 Correct 35 ms 23860 KB Output is correct
17 Correct 30 ms 23864 KB Output is correct
18 Correct 39 ms 23844 KB Output is correct
19 Correct 43 ms 23960 KB Output is correct
20 Correct 30 ms 23880 KB Output is correct
21 Correct 43 ms 23864 KB Output is correct
22 Correct 41 ms 23876 KB Output is correct
23 Correct 28 ms 23996 KB Output is correct
24 Correct 44 ms 23928 KB Output is correct
25 Correct 44 ms 23900 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 316 ms 25568 KB Output is correct
2 Correct 332 ms 25588 KB Output is correct
3 Correct 325 ms 25560 KB Output is correct
4 Correct 292 ms 25696 KB Output is correct
5 Correct 259 ms 25632 KB Output is correct
6 Correct 338 ms 25568 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 287 ms 25600 KB Output is correct
2 Correct 325 ms 25664 KB Output is correct
3 Correct 323 ms 25716 KB Output is correct
4 Correct 800 ms 31856 KB Output is correct
5 Correct 368 ms 26088 KB Output is correct
6 Correct 310 ms 26060 KB Output is correct
7 Correct 203 ms 26316 KB Output is correct
8 Correct 410 ms 26384 KB Output is correct
9 Correct 349 ms 26500 KB Output is correct
10 Correct 482 ms 27268 KB Output is correct
11 Correct 294 ms 25780 KB Output is correct