oj.uz

Submission #521701

# Submission time Handle Problem Language Result Execution time Memory
521701 2022-02-02T18:36:14 Z tkwiatkowski Zagrade (COI20_zagrade) C++17
100 / 100
 895 ms 832 KB 
/*
	Zadanie: Zagrade
	Autor: Tomasz Kwiatkowski
*/

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 7;

int L[MAXN];

bool correct(int l, int r)
{
	cout << "? " << l + 1 << ' ' << r + 1 << '\n';
	cout.flush();
	bool ans;
	cin >> ans;
	return ans;
}

void solve()
{
	int N, Q;
	cin >> N >> Q;
	for (int i = 1; i < N; ++i)
		L[i] = i - 1;

	int par_left = N;

	string ans(N, '#');
	for (int i = 1; i < N; ++i) {
		if (correct(L[i], i)) {
			ans[L[i]] = '(';
			ans[i] = ')';
			par_left -= 2;
			L[i + 1] = L[L[i]];
		}
	}

	int k = 0;
	for (int i = 0; i < N; ++i) {
		if (ans[i] == '#')
			ans[i] = (++k <= par_left/2 ? ')' : '(');
	}

	cout << "! " << ans << '\n';
	cout.flush();
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0);

	solve();

	return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 312 KB Output is correct
2 Correct 11 ms 200 KB Output is correct
3 Correct 10 ms 200 KB Output is correct
4 Correct 10 ms 200 KB Output is correct
5 Correct 9 ms 288 KB Output is correct
6 Correct 9 ms 200 KB Output is correct
7 Correct 10 ms 200 KB Output is correct
8 Correct 9 ms 200 KB Output is correct

Subtask #2
7.0 / 7.0

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

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 875 ms 792 KB Output is correct
3 Correct 764 ms 780 KB Output is correct
4 Correct 895 ms 788 KB Output is correct
5 Correct 763 ms 832 KB Output is correct
6 Correct 817 ms 816 KB Output is correct
7 Correct 704 ms 780 KB Output is correct
8 Correct 573 ms 780 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 611 ms 780 KB Output is correct
3 Correct 752 ms 788 KB Output is correct
4 Correct 506 ms 776 KB Output is correct
5 Correct 677 ms 796 KB Output is correct
6 Correct 794 ms 780 KB Output is correct
7 Correct 635 ms 780 KB Output is correct
8 Correct 767 ms 788 KB Output is correct