Submission #1218366

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218366		fast	Worm Worries (BOI18_worm)	C++20	0 / 100	1 ms	460 KiB

worm

#include "bits/stdc++.h"
using namespace std;

#define vec vector
#define int long long
#define all(x) (x).begin(), (x).end()

const int mod = 1e9 + 7;
const int inf = LLONG_MAX;

using pii = pair<int, int>;

int n, m, k, q;

int cache[1000'100] = {0};
bool done[1000'100] = {false};
int ask(int x) {
	if (x < 1 || x > n) return 0;

	if (done[x]) return cache[x];
	done[x] = true;
	cout << "? " << x << " 1 1\n";
	cout.flush();
	
	done[x] = true;
	cin >> x;
	return cache[x] = x;
}


int ans(int x) {
	cout << "! " << x << " 1 1\n";
	cout.flush();
	exit(0);
}

enum Slope {
	Increasing,
	Decreasing,
};

Slope slope(int x) {
	int a = ask(x - 1);
	int b = ask(x);
	int c = ask(x + 1);

	if (b >= a && b >= c) ans(x);
	if (a <= b && b <= c) return Increasing;
	if (a >= b && b >= c) return Decreasing;

	assert(false);
}

int solve(int a, int b) {
	if (b - a + 1 <= 100) {
		for(int i = a; i <= b; i++) slope(i);
	}

	int mid = (a + b) / 2;
	if (slope(mid) == slope(a)) return solve(mid, b);
	else return solve(a, mid);
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);


	cin >> n >> m >> k >> q;
	slope(1);
	slope(n);

}

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