Submission #594984

#	Time	Username	Problem	Language	Result	Execution time	Memory
594984		Cantfindme	Zagrade (COI20_zagrade)	C++17	100 / 100	815 ms	2056 KiB

zagrade

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pi;
#define f first
#define s second
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);
#define all(x) x.begin(),x.end()

const int maxn = 100010;
const int INF = LLONG_MAX/2;
const int mod = 1e9+7;

// string s = ")(())(()))((()";

bool check(int a, int b) {
	// int co = 0;
	// cout << a << " " << b << " ";
	// for (int i = a; i <= b;i++) {
	// 	if (s[i-1] == '(') co += 1;
	// 	else co -= 1;
	// 	if (co < 0) {
	// 		cout << "0\n";
	// 		return false;
	// 	}
	// }
	// if (co == 0) {
	// 	cout << "1\n";
	// 	return true;
	// } else {
	// 	cout << "0\n";
	// 	return false;
	// }

	cout << "? " << a << " " << b << "\n";
	cout.flush();
	int x; cin >> x;
	return x;
}

int32_t main() {
	FAST
	// ifstream cin("input.txt");

	int n, Q; cin >> n >> Q;
	stack <int> S;
	S.push(1);
	vector <int> ans(n+1, 0);

	for (int i =2;i<=n;i++) {
		if (!S.empty() and check(S.top(), i)) {
			ans[S.top()] = 1;
			ans[i] = 2;
			S.pop();
		} else {
			S.push(i);
		}
	}

	int left = S.size();
	for (int i =0;i<left/2;i++) {
		ans[S.top()] = 1; S.pop();
	}

	for (int i =0;i<left/2;i++) {
		ans[S.top()] = 2; S.pop();
	}

	cout << "! ";
	for (int i =1;i<=n;i++) {
		if (ans[i] == 1) cout << '(';
		else cout << ')';
	}
}

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