Submission #521701

#	Time	Username	Problem	Language	Result	Execution time	Memory
521701		tkwiatkowski	Zagrade (COI20_zagrade)	C++17	100 / 100	895 ms	832 KiB

zagrade

/*
	Zadanie: Zagrade
	Autor: Tomasz Kwiatkowski
*/

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

const int MAXN = 1e5 + 7;

int L[MAXN];

bool correct(int l, int r)
{
	cout << "? " << l + 1 << ' ' << r + 1 << '\n';
	cout.flush();
	bool ans;
	cin >> ans;
	return ans;
}

void solve()
{
	int N, Q;
	cin >> N >> Q;
	for (int i = 1; i < N; ++i)
		L[i] = i - 1;

	int par_left = N;

	string ans(N, '#');
	for (int i = 1; i < N; ++i) {
		if (correct(L[i], i)) {
			ans[L[i]] = '(';
			ans[i] = ')';
			par_left -= 2;
			L[i + 1] = L[L[i]];
		}
	}

	int k = 0;
	for (int i = 0; i < N; ++i) {
		if (ans[i] == '#')
			ans[i] = (++k <= par_left/2 ? ')' : '(');
	}

	cout << "! " << ans << '\n';
	cout.flush();
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0);

	solve();

	return 0;
}

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