Submission #1152385

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152385		siewjh	Zagrade (COI20_zagrade)	C++20	100 / 100	223 ms	884 KiB

zagrade

#include <bits/stdc++.h>
using namespace std;
int main(){
	int nums, q; cin >> nums >> q;
	stack<pair<int, int>> st;
	vector<int> ans(nums + 1, -1);
	int rem = nums >> 1;
	for (int i = 2; i <= nums; i++){
		int res, lb;
		if (!st.empty() && st.top().second == i - 1){
			if (st.top().first == 1) continue;
			lb = st.top().first - 1;
		}
		else lb = i - 1;
		cout << "? " << lb << ' ' << i << endl;
		cin >> res;
		if (res){
			ans[lb] = 0; ans[i] = 1; rem--;
			if (!st.empty() && st.top().second == i - 1) st.pop();
			if (!st.empty() && st.top().second == lb - 1){
				lb = st.top().first;
				st.pop();
			}
			st.push({lb, i});
		}
	}
	cout << "! ";
	for (int i = 1; i <= nums; i++){
		if (ans[i] == -1){
			if (rem){
				ans[i] = 1; rem--;
			}
			else ans[i] = 0;
		}
		cout << (ans[i] ? ')' : '(');
	}
	cout << endl;
}

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