Submission #1149413

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149413		Pwo	Zagrade (COI20_zagrade)	C++20	14 / 100	836 ms	772 KiB

zagrade

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

int n, q;
char ch[100005];

int ask(int i, int j) {
	cout << "? " << i << ' ' << j << endl;
	int res; cin >> res;
	return res;
}

int32_t main() {
	cin >> n >> q;
	for (int i = 1; i <= n; i++) ch[i] = '.';
	for (int i = 1; i < n; i++) {
		if (ch[i] != '.') continue;
		for (int j = i + 1; j <= n; j += 2) {
			if (ch[j] != '.') continue;
			if (q < 0) return 0;
			q--;
			int res = ask(i, j);
			if (res) {
				ch[i] = '(';
				ch[j] = ')';
			}
		}
	}

	int cnt = 0;
	for (int i = 1; i <= n; i++) if (ch[i] == ')') cnt++;
	string s = "";
	for (int i = 1; i <= n; i++) {
		if (ch[i] != '.') s += ch[i];
		else if (cnt * 2 < n) {
			s += ')';
			cnt++;
		} else s += '(';
	}
	cout << "! " << s << endl;
}

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