Submission #647522

#	Time	Username	Problem	Language	Result	Execution time	Memory
647522		fatemetmhr	Worm Worries (BOI18_worm)	C++17	22 / 100	88 ms	728 KiB

worm

// ~ 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;

#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 ll  inf   =  1e18;


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

    
    cin >> n >> m >> k >> q;
    int tt = 100;
    while(tt--){
        int x = rng() % n + 1, y = rng() % m + 1;
        if(av.find({x, y}) != av.end()){
            tt++;
            continue;
        }
        ask(x, y);
    }

    int x = mxx, y = mxy;
    while(true){
        shuffle(nei, nei + 4, rng);
        int mx = 4; ans[4] = av[mp(x, y)];
        for(int i = 0; i < 4; i++){
            ans[i] = ask(x + nei[i].fi, y + nei[i].se);
            if(ans[i] > ans[mx]){
                mx = i;
                break;
            }
        }
        if(mx == 4){
            cout << "! " << x << ' ' << y << ' ' << 1 << endl;
            return 0;
        }
        x += nei[mx].fi;
        y += nei[mx].se;
    }

}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 22
• Subtask 3: 12 / 12
• Subtask 4: 0 / 19
• Subtask 5: 0 / 14
• Subtask 6: 0 / 23