Submission #1003843

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003843		vjudge1	Zagrade (COI20_zagrade)	C++17	100 / 100	592 ms	1324 KiB

zagrade

#include <bits/stdc++.h>

using namespace std;

int main() {
	int n, q;
	cin >> n >> q;

	function<bool (int, int)> query = [](int l, int r) {
		cout << "? " << l + 1 << " " << r + 1 << endl;

		int x;
		cin >> x;

		return x;
	};

	string s(n, '0');

	stack<pair<int, int>> inters; int cnt = 0;
	for (int i = 0; i < n-1; ++i) {
		if (query(i, i + 1)) {
			s[i] = '('; s[i+1] = ')'; ++cnt;

			int l = i, r = i + 1;
			while (true) {
				if (!inters.empty()) {
					auto [l1, r1] = inters.top();

					if (r1 == l - 1) { l = l1; inters.pop(); }
				}

				if (l > 0 && r < n - 1 && query(l - 1, r + 1)) {
					--l; ++r;
					s[l] = '('; s[r] = ')'; ++cnt;
				}
				else break;
			}

			inters.emplace(l, r);

			i = r;
		}
	}

	int falta = n/2 - cnt;
	for (char &c: s)
		if (c == '0') 
			if (falta > 0) { c = ')'; -- falta; }
			else c = '(';

	cout << "! " << s << "\n";
}

Compilation message (stderr)

zagrade.cpp: In function 'int main()':
zagrade.cpp:48:6: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   48 |   if (c == '0')
      |      ^

• Subtask 1: 14 / 14
• Subtask 2: 7 / 7
• Subtask 3: 57 / 57
• Subtask 4: 22 / 22