oj.uz

Submission #773869

# Submission time Handle Problem Language Result Execution time Memory
773869 2023-07-05T09:13:16 Z vjudge1 Zagrade (COI20_zagrade) C++17
100 / 100
 865 ms 1100 KB 
 #include <bits/stdc++.h>
using namespace std;
#define sp " "
//#define endl "\n"
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define N 200005

int ask(int a, int b){
	cout<<"? "<<a<<sp<<b<<endl;
	int res;
	cin>>res;
	return res;
}


int32_t main(){
	//fileio();
	//fastio();

	int n, q;
	cin>>n>>q;


	vector<int> arr(n + 5, 0);
	map<int ,int> pos;
	int curr = 0, it = 2;
	stack<int> last;
	last.push(1);
	while(it <= n){
		if (last.empty())
		{
			last.push(it);
			it++;
			continue;
		}
		int res = ask(last.top(), it);
		if (res){
			arr[last.top()] = 1, arr[it] = -1;
			last.pop();
		}
		else last.push(it);
		it++;
	}
	
	int m = last.size();
	int tmp = m / 2;
	while(tmp > 0){
		arr[last.top()] = 1;
		last.pop();
		tmp--;
	}

	while(last.size()){
		arr[last.top()] = -1;
		last.pop();
	}
	cout<<"! ";
	for (int i = 1; i <= n; i++){
		cout<<((arr[i] == 1) ? '(' : ')');
	}
	cout<<endl;
	//cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<" seconds\n";
}

Compilation message

zagrade.cpp: In function 'int32_t main()':
zagrade.cpp:31:6: warning: unused variable 'curr' [-Wunused-variable]
   31 |  int curr = 0, it = 2;
      |      ^~~~

Subtask #1
14.0 / 14.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 6 ms 208 KB Output is correct
3 Correct 4 ms 208 KB Output is correct
4 Correct 7 ms 284 KB Output is correct
5 Correct 4 ms 208 KB Output is correct
6 Correct 7 ms 208 KB Output is correct
7 Correct 6 ms 208 KB Output is correct
8 Correct 6 ms 208 KB Output is correct

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 330 ms 688 KB Output is correct
3 Correct 707 ms 592 KB Output is correct
4 Correct 624 ms 592 KB Output is correct
5 Correct 660 ms 684 KB Output is correct
6 Correct 682 ms 592 KB Output is correct
7 Correct 708 ms 880 KB Output is correct
8 Correct 397 ms 592 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 580 ms 1100 KB Output is correct
3 Correct 771 ms 760 KB Output is correct
4 Correct 609 ms 888 KB Output is correct
5 Correct 609 ms 744 KB Output is correct
6 Correct 865 ms 888 KB Output is correct
7 Correct 665 ms 704 KB Output is correct
8 Correct 809 ms 592 KB Output is correct