oj.uz

Submission #1003738

# Submission time Handle Problem Language Result Execution time Memory
1003738 2024-06-20T16:37:44 Z vjudge1 Zagrade (COI20_zagrade) C++17
100 / 100
 622 ms 1124 KB 
#include<bits/stdc++.h>
#define endl '\n'

using namespace std;

const int N = 100010;

struct LinkedList{
	int lt[N], rt[N];
	LinkedList(int n){
		for(int i = 1;i <= n;i++){
			lt[i] = i-1;
			rt[i] = i+1;
		}
	}
	void remove(int x){
		int l = lt[x], r = rt[x];
		rt[l] = r;
		lt[r] = l;
		return;
	}
	int left(int n){
		return lt[n];
	}
	int right(int n){
		return rt[n];
	}
};

char res[N];

int main(){
	int n, q;
	cin >> n >> q;
	LinkedList v(n);
	int qtd0 = 0, qtd1 = 0;
	for(int i = 1;i <= n;i++){
		res[i] = '0';
	}
	for(int i = 2;i <= n;i++){
		int l = v.left(i);
		if(l == 0) continue;
		cout << "? " << l << ' ' << i << endl;
		cout << flush;
		int x;
		cin >> x;
		if(x == 1){
			v.remove(l);
			v.remove(i);
			res[l] = '(';
			res[i] = ')';
			qtd0++;
			qtd1++;
		}
	}
	qtd0 = n/2-qtd0;
	qtd1 = n/2-qtd1;
	for(int i = 1;i <= n;i++){
		if(res[i] == '0'){
			if(qtd1){
				qtd1--;
				res[i] = ')';
			}
			else{
				qtd0--;
				res[i] = '(';
			}
		}
	}
	cout << "! ";
	for(int i = 1;i <= n;i++){
		cout << res[i];
	}
	cout << endl << flush;
	return 0;
}

Subtask #1
14.0 / 14.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1112 KB Output is correct
2 Correct 295 ms 1112 KB Output is correct
3 Correct 622 ms 1124 KB Output is correct
4 Correct 584 ms 1112 KB Output is correct
5 Correct 610 ms 1112 KB Output is correct
6 Correct 499 ms 1112 KB Output is correct
7 Correct 514 ms 1112 KB Output is correct
8 Correct 546 ms 1112 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1112 KB Output is correct
2 Correct 525 ms 1112 KB Output is correct
3 Correct 551 ms 1112 KB Output is correct
4 Correct 535 ms 1112 KB Output is correct
5 Correct 510 ms 1112 KB Output is correct
6 Correct 566 ms 1112 KB Output is correct
7 Correct 516 ms 1112 KB Output is correct
8 Correct 527 ms 1112 KB Output is correct