oj.uz

Submission #312580

# Submission time Handle Problem Language Result Execution time Memory
312580 2020-10-13T19:29:28 Z Lawliet Zagrade (COI20_zagrade) C++17
100 / 100
 1055 ms 1340 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 100010;

int n, q;

string ans;

bool query(int L, int R)
{
	L++; R++;
	cout << "? " << L << " " << R << endl;

	int a;
	cin >> a;

	return a;
}

void answer()
{
	cout << "! " << ans << endl;
	exit(0);
}

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

	ans.resize( n );
	vector<int> s( 1 , 0 );

	for(int i = 1 ; i < n ; i++)
	{
		if( query( s.back() , i ) )
		{
			ans[ s.back() ] = '(';
			ans[i] = ')';

			s.pop_back();
		}
		else s.push_back( i );
	}

	int qtd = (int)s.size(); qtd /= 2;

	for(int i = 0 ; i < qtd ; i++)
		ans[ s.back() ] = '(', s.pop_back();

	for(int i = 0 ; i < qtd ; i++)
		ans[ s.back() ] = ')', s.pop_back();

	answer();
}

Subtask #1
14.0 / 14.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 848 ms 504 KB Output is correct
3 Correct 776 ms 504 KB Output is correct
4 Correct 995 ms 504 KB Output is correct
5 Correct 800 ms 472 KB Output is correct
6 Correct 878 ms 468 KB Output is correct
7 Correct 1020 ms 888 KB Output is correct
8 Correct 1045 ms 468 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 834 ms 1340 KB Output is correct
3 Correct 1027 ms 908 KB Output is correct
4 Correct 813 ms 1044 KB Output is correct
5 Correct 853 ms 1016 KB Output is correct
6 Correct 914 ms 888 KB Output is correct
7 Correct 1055 ms 760 KB Output is correct
8 Correct 777 ms 464 KB Output is correct