Submission #530426

#	Time	Username	Problem	Language	Result	Execution time	Memory
530426		fatemetmhr	Worm Worries (BOI18_worm)	C++17	0 / 100	59 ms	888 KiB

worm

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

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


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

const int maxn5 = 3e5 + 10;
map <pair<int, int>, ll> av;
vector <pair<int, int>> qu;

int n, m, k, q;


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}];
	return av[{x, y}];
}

inline pair <int, int> check(int x, int y){
	shuffle(all(qu), rng);
	for(auto [a, b] : qu)
		if(ask(x, y) < ask(x + a, y + b))
			return {x + a, y + b};
	cout << "! " << x << ' ' << y << ' ' << 1 << endl;
	exit(0);
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	cin >> n >> m >> k >> q;
	int x = rng() % n + 1, y = rng() % m + 1;
	qu.pb({0, 1});
	qu.pb({0, -1});
	qu.pb({1, 0});
	qu.pb({-1, 0});
	while(true){
		pair <int, int> tmp = check(x, y);
		x = tmp.fi;
		y = tmp.se;
	}
}

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