oj.uz

Submission #411825

# Submission time Handle Problem Language Result Execution time Memory
411825 2021-05-26T04:36:57 Z 장태환(#7564) Zagrade (COI20_zagrade) C++17
100 / 100
 1170 ms 888 KB 
#include <iostream>
#include <algorithm>
#include <stack>
#include <string>
using namespace std;
int main()
{
	int N,Q;
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N >> Q;
	stack<int>s;
	int i;
	string res(N,'0');
	for (i = 1; i <= N; i++)
	{
		if (!s.size())
		{
			s.push(i);
		}
		else
		{
			cout << '?' << ' ' << s.top() << ' ' << i << '\n';
			cout.flush();
			int r;
			cin >> r;
			if (r == 1)
			{
				res[s.top()-1] = '(';
				res[i-1] = ')';
				s.pop();
			}
			else
			{
				s.push(i);
			}
		}
	}
	int unq = 0;
	for (i = 0; i < N; i++)
	{
		unq += res[i] == '0';
	}
	int cu = 0;
	for (i = 0; i < N; i++)
	{
		if (res[i] == '0')
		{
			if (cu * 2 >= unq)
				res[i] = '(';
			else
				res[i] = ')';
			cu++;
		}
	}
	cout << '!' << ' ' << res;
	cout.flush();
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 7 ms 200 KB Output is correct
3 Correct 13 ms 208 KB Output is correct
4 Correct 13 ms 200 KB Output is correct
5 Correct 11 ms 256 KB Output is correct
6 Correct 5 ms 200 KB Output is correct
7 Correct 13 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 1 ms 200 KB Output is correct
2 Correct 11 ms 200 KB Output is correct
3 Correct 14 ms 304 KB Output is correct
4 Correct 13 ms 200 KB Output is correct
5 Correct 14 ms 304 KB Output is correct
6 Correct 13 ms 200 KB Output is correct
7 Correct 8 ms 200 KB Output is correct
8 Correct 12 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 491 ms 392 KB Output is correct
3 Correct 720 ms 384 KB Output is correct
4 Correct 799 ms 448 KB Output is correct
5 Correct 810 ms 392 KB Output is correct
6 Correct 633 ms 388 KB Output is correct
7 Correct 962 ms 600 KB Output is correct
8 Correct 914 ms 384 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 775 ms 820 KB Output is correct
3 Correct 998 ms 572 KB Output is correct
4 Correct 1170 ms 668 KB Output is correct
5 Correct 1002 ms 704 KB Output is correct
6 Correct 736 ms 888 KB Output is correct
7 Correct 886 ms 600 KB Output is correct
8 Correct 957 ms 384 KB Output is correct