Submission #1003902

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003902		vjudge1	Zagrade (COI20_zagrade)	C++17	100 / 100	617 ms	1676 KiB

zagrade

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

int query(int a, int b, int &Q)
{
	cout << "? " << a << " " << b << endl;
	int resp; cin >> resp;
	return resp;
}

void solve(int N, int Q)
{
	string resp(N, '.');
	vector<int> resto;
	for (int i = 1; i <= N; i++)
	{
		if (resto.empty()) resto.push_back(i);
		else if(query(resto.back(), i, Q))
		{
			resp[resto.back()-1] = '(';
			resp[i-1] = ')';
			resto.pop_back();
		}
		else resto.push_back(i);
	}
	// cerr << "resp: " << resp << '\n';
	// cerr << "resto: "; for (auto x : resto) cerr << " "; cerr << '\n';
	int sz = resto.size();
	for (int i = 0; i < sz/2; i++) resp[resto[i]-1] = ')';
	for (int i = sz/2; i < sz; i++) resp[resto[i]-1] = '(';
	cout << "! " << resp << endl;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int N, Q;
	cin >> N >> Q;
	solve(N, Q);
}

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