oj.uz

Submission #1003843

# Submission time Handle Problem Language Result Execution time Memory
1003843 2024-06-20T18:52:32 Z vjudge1 Zagrade (COI20_zagrade) C++17
100 / 100
 592 ms 1324 KB 
#include <bits/stdc++.h>

using namespace std;

int main() {
	int n, q;
	cin >> n >> q;

	function<bool (int, int)> query = [](int l, int r) {
		cout << "? " << l + 1 << " " << r + 1 << endl;

		int x;
		cin >> x;

		return x;
	};

	string s(n, '0');

	stack<pair<int, int>> inters; int cnt = 0;
	for (int i = 0; i < n-1; ++i) {
		if (query(i, i + 1)) {
			s[i] = '('; s[i+1] = ')'; ++cnt;

			int l = i, r = i + 1;
			while (true) {
				if (!inters.empty()) {
					auto [l1, r1] = inters.top();

					if (r1 == l - 1) { l = l1; inters.pop(); }
				}

				if (l > 0 && r < n - 1 && query(l - 1, r + 1)) {
					--l; ++r;
					s[l] = '('; s[r] = ')'; ++cnt;
				}
				else break;
			}

			inters.emplace(l, r);

			i = r;
		}
	}

	int falta = n/2 - cnt;
	for (char &c: s)
		if (c == '0') 
			if (falta > 0) { c = ')'; -- falta; }
			else c = '(';

	cout << "! " << s << "\n";
}

Compilation message

zagrade.cpp: In function 'int main()':
zagrade.cpp:48:6: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   48 |   if (c == '0')
      |      ^

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 3 ms 344 KB Output is correct
3 Correct 4 ms 344 KB Output is correct
4 Correct 5 ms 344 KB Output is correct
5 Correct 5 ms 344 KB Output is correct
6 Correct 5 ms 344 KB Output is correct
7 Correct 5 ms 344 KB Output is correct
8 Correct 4 ms 344 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 6 ms 344 KB Output is correct
3 Correct 5 ms 596 KB Output is correct
4 Correct 6 ms 436 KB Output is correct
5 Correct 6 ms 344 KB Output is correct
6 Correct 5 ms 600 KB Output is correct
7 Correct 6 ms 596 KB Output is correct
8 Correct 4 ms 344 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 265 ms 512 KB Output is correct
3 Correct 500 ms 512 KB Output is correct
4 Correct 538 ms 516 KB Output is correct
5 Correct 442 ms 512 KB Output is correct
6 Correct 592 ms 512 KB Output is correct
7 Correct 555 ms 508 KB Output is correct
8 Correct 512 ms 512 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 514 ms 528 KB Output is correct
3 Correct 486 ms 592 KB Output is correct
4 Correct 536 ms 772 KB Output is correct
5 Correct 491 ms 1052 KB Output is correct
6 Correct 542 ms 1324 KB Output is correct
7 Correct 525 ms 1044 KB Output is correct
8 Correct 545 ms 516 KB Output is correct