Submission #320896

#	Time	Username	Problem	Language	Result	Execution time	Memory
320896		dolphingarlic	Zagrade (COI20_zagrade)	C++14	100 / 100	1244 ms	888 KiB

zagrade

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

bool guess(int a, int b) {
	cout << "? " << a << ' ' << b << endl;
	bool res;
	cin >> res;
	return res;
}

char ans[100001];

int main() {
	int n, q, rem;
	cin >> n >> q;
	rem = n / 2;
	stack<int> stck;
	for (int i = 1; i <= n; i++) {
		if (!stck.size()) stck.push(i);
		else if (guess(stck.top(), i)) {
			ans[stck.top()] = '(';
			ans[i] = ')';
			stck.pop();
			rem--;
		} else stck.push(i);
	}
	cout << "! ";
	for (int i = 1; i <= n; i++) {
		if (ans[i] == '(' || ans[i] == ')') cout << ans[i];
		else if (rem) {
			cout << ')';
			rem--;
		} else cout << '(';
	}
	cout << endl;
	return 0;
}

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