Submission #865813

#	Time	Username	Problem	Language	Result	Execution time	Memory
865813		serifefedartar	Zagrade (COI20_zagrade)	C++17	100 / 100	553 ms	2120 KiB

zagrade

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 998244353;
const ll LOGN = 20; 
const ll MAXN = 3e5 + 100;

int ask(int l, int r) {
	cout << "? " << l << " " << r << endl;
	cout.flush();
	int x; cin >> x;
	return x;
}

void answer(string s) {
	cout << "! " << s << endl;
	cout.flush();
	exit(0);
}

int main() {
	fast
	int N, Q;
	cin >> N >> Q;

	stack<int> st;
	string ans;
	for (int i = 1; i <= N; i++) {
		if (st.empty()) {
			st.push(i);
			ans += '(';
		} else {
			int x = ask(st.top(), i);
			if (x) {
				st.pop();
				ans += ')';
			} else {
				st.push(i);
				ans += '(';
			}
		}
	}

	int n = st.size();
	for (int i = 0; i < n/2; i++) {
		ans[st.top() - 1] = '(';
		st.pop();
	}
	for (int i = 0; i < n/2; i++) {
		ans[st.top() - 1] = ')';
		st.pop();
	}

	answer(ans);
}

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