oj.uz

Submission #594984

# Submission time Handle Problem Language Result Execution time Memory
594984 2022-07-13T08:30:44 Z Cantfindme Zagrade (COI20_zagrade) C++17
100 / 100
 815 ms 2056 KB 
#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.0 / 14.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 8 ms 324 KB Output is correct
3 Correct 7 ms 208 KB Output is correct
4 Correct 9 ms 208 KB Output is correct
5 Correct 7 ms 208 KB Output is correct
6 Correct 8 ms 320 KB Output is correct
7 Correct 14 ms 260 KB Output is correct
8 Correct 11 ms 208 KB Output is correct

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 434 ms 1104 KB Output is correct
3 Correct 692 ms 1104 KB Output is correct
4 Correct 650 ms 1120 KB Output is correct
5 Correct 753 ms 1104 KB Output is correct
6 Correct 730 ms 1104 KB Output is correct
7 Correct 610 ms 1588 KB Output is correct
8 Correct 779 ms 1104 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 709 ms 2056 KB Output is correct
3 Correct 704 ms 1364 KB Output is correct
4 Correct 606 ms 1656 KB Output is correct
5 Correct 788 ms 1320 KB Output is correct
6 Correct 815 ms 1572 KB Output is correct
7 Correct 345 ms 1316 KB Output is correct
8 Correct 730 ms 1104 KB Output is correct