Submission #724625

#	Time	Username	Problem	Language	Result	Execution time	Memory
724625		tutis	Worm Worries (BOI18_worm)	C++17	32 / 100	1 ms	312 KiB

worm

/*input
1000000 1 1 29

*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
template<typename T, typename M>
using oset = tree<T, M, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const ll mod = 1e9 + 7;
ll power(ll x, ll y)
{
	if (abs(x) >= mod)
		x %= mod;
	if (x < 0)
		x += mod;
	if (abs(y) >= mod - 1)
		y %= mod - 1;
	if (y < 0)
		y += mod - 1;
	if (y == 0)
		return 1;
	while (y % 2 == 0)
	{
		x = (x * x) % mod;
		y /= 2;
	}
	ll r = x;
	y /= 2;
	while (y)
	{
		x = (x * x) % mod;
		if (y % 2 == 1)
			r = (r * x) % mod;
		y /= 2;
	}
	return r;
}
int N, M, K, Q;
map<tuple<int, int, int>, int>H;
int q(int i, int j = 1, int k = 1)
{
	if (i > N)
		return -i;
	if (i < 1)
		return -1 + i;
	if (H.count({i, j, k}))
		return H[ {i, j, k}];
	Q--;
	assert(Q >= 0);
	cout << "? " << i << " " << j << " " << k << endl;
	int h;
	cin >> h;
	return H[ {i, j, k}] = h;
}
void solve()
{
	int x[40], y[40];
	x[0] = 1;
	y[0] = 0;
	for (int t = 1; t < 40; t++)
	{
		x[t] = y[t - 1] + x[t - 1] + 1;
		y[t] = x[t - 1] - 1;
	}
	cin >> N >> M >> K >> Q;
	int t = 0;
	while (x[t] * 2 + y[t] < N)
		t++;
	int lo = 1;
	int hi = x[t] * 2 + y[t];
	while (lo < hi)
	{
		if (q(lo + x[t] - 1) > q(hi - x[t] + 1))
			hi -= x[t];
		else
			lo += x[t];
		t--;
	}
	cout << "! " << lo << " 1 1" << endl;
	cerr << Q << endl;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	solve();
}

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