oj.uz

Submission #865813

# Submission time Handle Problem Language Result Execution time Memory
865813 2023-10-24T17:47:39 Z serifefedartar Zagrade (COI20_zagrade) C++17
100 / 100
 553 ms 2120 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 998244353;
const ll LOGN = 20; 
const ll MAXN = 3e5 + 100;

int ask(int l, int r) {
	cout << "? " << l << " " << r << endl;
	cout.flush();
	int x; cin >> x;
	return x;
}

void answer(string s) {
	cout << "! " << s << endl;
	cout.flush();
	exit(0);
}

int main() {
	fast
	int N, Q;
	cin >> N >> Q;

	stack<int> st;
	string ans;
	for (int i = 1; i <= N; i++) {
		if (st.empty()) {
			st.push(i);
			ans += '(';
		} else {
			int x = ask(st.top(), i);
			if (x) {
				st.pop();
				ans += ')';
			} else {
				st.push(i);
				ans += '(';
			}
		}
	}

	int n = st.size();
	for (int i = 0; i < n/2; i++) {
		ans[st.top() - 1] = '(';
		st.pop();
	}
	for (int i = 0; i < n/2; i++) {
		ans[st.top() - 1] = ')';
		st.pop();
	}

	answer(ans);
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 4 ms 344 KB Output is correct
4 Correct 4 ms 600 KB Output is correct
5 Correct 3 ms 600 KB Output is correct
6 Correct 3 ms 600 KB Output is correct
7 Correct 3 ms 344 KB Output is correct
8 Correct 3 ms 600 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 4 ms 856 KB Output is correct
3 Correct 4 ms 600 KB Output is correct
4 Correct 4 ms 708 KB Output is correct
5 Correct 4 ms 852 KB Output is correct
6 Correct 4 ms 456 KB Output is correct
7 Correct 3 ms 604 KB Output is correct
8 Correct 3 ms 600 KB Output is correct

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 230 ms 1624 KB Output is correct
3 Correct 521 ms 1660 KB Output is correct
4 Correct 525 ms 1508 KB Output is correct
5 Correct 553 ms 1520 KB Output is correct
6 Correct 513 ms 1320 KB Output is correct
7 Correct 519 ms 1952 KB Output is correct
8 Correct 463 ms 2024 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 499 ms 2120 KB Output is correct
3 Correct 464 ms 1260 KB Output is correct
4 Correct 471 ms 1968 KB Output is correct
5 Correct 464 ms 1792 KB Output is correct
6 Correct 534 ms 1900 KB Output is correct
7 Correct 532 ms 1816 KB Output is correct
8 Correct 494 ms 1232 KB Output is correct