Submission #345452

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
345452	2021-01-07T11:10:02 Z	pggp	Zagrade (COI20_zagrade)	C++14	100 / 100	1240 ms	900 KB

zagrade

#include <bits/stdc++.h>

using namespace std;

int N, Q;
char output[250000];

int main(){
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(false);
	for (int i = 0; i < N; ++i)
	{
		output[i] = '?';
	}

	cin >> N >> Q;
	stack < int > last_non_valid;
	for (int i = 0; i < N; ++i)
	{
		if(last_non_valid.empty()){
			last_non_valid.push(i);
			continue;
		}
		cout << "? " << last_non_valid.top() + 1 << " " << i + 1 << endl;
		bool valid;
		cin >> valid;
		if(valid){
			output[last_non_valid.top()] = '(';
			output[i] = ')';
			last_non_valid.pop();
		}
		else{
			last_non_valid.push(i);
		}
	}
	int s = last_non_valid.size();
	for (int i = 0; i < s/2; ++i)
	{
		output[last_non_valid.top()] = '(';
		last_non_valid.pop();
	}
	for (int i = s/2; i < s; ++i)
	{
		output[last_non_valid.top()] = ')';
		last_non_valid.pop();
	}

	cout << "! ";

	for (int i = 0; i < N; ++i)
	{
		cout << output[i];
	}
	cout << endl;
}

Subtask #1

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	5 ms	364 KB	Output is correct
3	Correct	6 ms	364 KB	Output is correct
4	Correct	5 ms	364 KB	Output is correct
5	Correct	12 ms	364 KB	Output is correct
6	Correct	10 ms	308 KB	Output is correct
7	Correct	14 ms	400 KB	Output is correct
8	Correct	8 ms	364 KB	Output is correct

Subtask #2

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	10 ms	364 KB	Output is correct
3	Correct	16 ms	364 KB	Output is correct
4	Correct	14 ms	400 KB	Output is correct
5	Correct	13 ms	364 KB	Output is correct
6	Correct	14 ms	400 KB	Output is correct
7	Correct	10 ms	364 KB	Output is correct
8	Correct	10 ms	364 KB	Output is correct

Subtask #3

57.0 / 57.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	410 ms	620 KB	Output is correct
3	Correct	722 ms	500 KB	Output is correct
4	Correct	773 ms	528 KB	Output is correct
5	Correct	1240 ms	652 KB	Output is correct
6	Correct	897 ms	580 KB	Output is correct
7	Correct	1032 ms	736 KB	Output is correct
8	Correct	955 ms	496 KB	Output is correct

Subtask #4

22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	742 ms	900 KB	Output is correct
3	Correct	1080 ms	572 KB	Output is correct
4	Correct	740 ms	700 KB	Output is correct
5	Correct	887 ms	624 KB	Output is correct
6	Correct	640 ms	752 KB	Output is correct
7	Correct	795 ms	668 KB	Output is correct
8	Correct	951 ms	588 KB	Output is correct