oj.uz

Submission #1003839

# Submission time Handle Problem Language Result Execution time Memory
1003839 2024-06-20T18:48:38 Z vjudge1 Zagrade (COI20_zagrade) C++17
71 / 100
 598 ms 596 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 - 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 1 ms 344 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 4 ms 344 KB Output is correct
4 Correct 4 ms 344 KB Output is correct
5 Correct 4 ms 344 KB Output is correct
6 Correct 4 ms 344 KB Output is correct
7 Correct 4 ms 344 KB Output is correct
8 Correct 4 ms 344 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Mismatch at position 2. Expected (, found )
2 Halted 0 ms 0 KB -

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 273 ms 512 KB Output is correct
3 Correct 539 ms 508 KB Output is correct
4 Correct 523 ms 508 KB Output is correct
5 Correct 544 ms 508 KB Output is correct
6 Correct 492 ms 512 KB Output is correct
7 Correct 528 ms 512 KB Output is correct
8 Correct 598 ms 508 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Mismatch at position 3. Expected (, found )
2 Halted 0 ms 0 KB -