Submission #928628

#	Time	Username	Problem	Language	Result	Execution time	Memory
928628		NK_	Zagrade (COI20_zagrade)	C++17	100 / 100	477 ms	1768 KiB

zagrade

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

using namespace std;

#define nl '\n'
#define sz(x) int(x.size())

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

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

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

	vi stk = {0};
	string ans(N, '?');
	for(int i = 1; i < N; i++) {
		if (qry(stk.back(), i)) {
			ans[stk.back()] = '(';
			ans[i] = ')';
			stk.pop_back();
		} else stk.push_back(i);
	}

	int M = sz(stk) / 2;
	for(int i = 0; i < M; i++) {
		ans[stk[i]] = ')';
		ans[stk[i + M]] = '(';
	}	

	cout << "! " << ans << endl;

	exit(0-0);
}

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