Submission #919490

#	Time	Username	Problem	Language	Result	Execution time	Memory
919490		NK_	Mađioničar (COI22_madionicar)	C++17	13 / 100	961 ms	860 KiB

Main

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'

template<class T> using V = vector<T>;
using vi = V<int>;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N; cin >> N;

	auto ask = [&](int l, int r) {
		if (l < 0 || r >= N) return 0;
		cout << "? " << l + 1 << " " << r + 1 << endl;
		int res; cin >> res; return res;
	};

	int ANS = 1;

	// odd
	{
		vi ans(N); int lo = 0, hi = 0;
		for(int i = 0; i < N; i++) {
			if (i > 0) {
				ans[i] = min(hi - i, ans[hi - i + lo]);
				ans[i] = max(0, ans[i]);
			}
			while(ask(i - ans[i] - 1, i + ans[i] + 1)) ++ans[i];
			if (ans[i] + i > hi) lo = i - ans[i], hi = i + ans[i];
		}

		// for(auto& x : ans) cout << x << " ";
		// cout << nl;

		int bst = *max_element(begin(ans), end(ans));
		ANS = max(ANS, 2 * bst + 1);
	}

	// even
	{
		vi ans(N, -1); int lo = 0, hi = 0;
		for(int i = 1; i < N; i++) {
			// cout << lo << " " << hi << " " << hi - i + 1 + lo << endl;
			if (i > 1) ans[i] = min(hi - i + 1, ans[hi - i + 1 + lo]);
			// cout << ans[i] << endl;

			while(ask(i - 1 - ans[i] - 1, i + ans[i] + 1)) ++ans[i];
			if (ans[i] + i > hi) lo = i - 1 - ans[i], hi = i + ans[i];
		}

		// for(auto& x : ans) cout << x << " ";
		// cout << nl;

		int bst = *max_element(begin(ans), end(ans));
		ANS = max(ANS, 2 * bst + 2);
	}

	cout << "! " << ANS << endl;



	exit(0-0);
}

• Subtask 1: 13 / 13
• Subtask 2: 0 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 37