Submission #1003738

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003738		vjudge1	Zagrade (COI20_zagrade)	C++17	100 / 100	622 ms	1124 KiB

zagrade

#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 / 14
• Subtask 2: 7 / 7
• Subtask 3: 57 / 57
• Subtask 4: 22 / 22