Submission #1152601

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152601		thelegendary08	Zagrade (COI20_zagrade)	C++17	100 / 100	240 ms	1556 KiB

zagrade

#include<bits/stdc++.h>
#define f0r(i,n) for(int i = 0; i<n; i++)
#define pb push_back
#define vi vector<long long int>
#define ll long long int
#define mp make_pair
#define pii pair<ll,ll>
#define FOR(i, k, n) for(int i = k; i<n; i++)
using namespace std;
bool ask(int a, int b){
	cout<<'?'<<' '<<a+1<<' '<<b+1<<endl;
	int x;
	cin>>x;
	return x;
}
int main(){
	int n,q;
	cin>>n>>q;
	vi ans(n,-1);

	ans[0] = 0;
	stack<int>opens;
	opens.push(0);
	FOR(i, 1, n){
		if(opens.empty()){
			ans[i] = 0;
			opens.push(i);
		}
		else{
			bool x = ask(opens.top(), i);
			if(x){
				ans[i] = 1;
				opens.pop();
			}
			else{
				ans[i] = 0;
				opens.push(i);
			}
		}
	}
	vector<bool>match(n);
	opens = stack<int>();
    f0r(i,n){
        if(ans[i] == 0){
            opens.push(i);
        }
        else{
            if(!opens.empty()){
                match[i] = 1;
                match[opens.top()] = 1;
                opens.pop();
            }
        }
    }
    int nomatch = 0;
    f0r(i,n){
        if(!match[i])nomatch++;
    }
    int cnt = 0;
    f0r(i,n){
        if(!match[i]){
            if(cnt < nomatch / 2){
                ans[i] = 1;
            }
            else ans[i] = 0;
            cnt++;
        }

    }
    /*
	for(int i = 2; i<=n; i+=2){
		f0r(j, n-i+1){
		    if(!(ans[j] == 1 || ans[j+i-1] == 0 || (ans[j] != -1 && ans[j+i-1] != -1))){
                bool b= ask(j, j+i-1);
                if(b){
                    ans[j] = 0;
                    ans[j+i-1] = 1;
                    //cout<<j<<' '<<j+i<<'\n';
                }
		    }

		}
	}
	int cnt = 0;
	f0r(i,n){
		if(ans[i] == -1){
			cnt++;
		}
	}
	int ct = 0;
	f0r(i,n){
		if(ans[i] == -1){
			if(ct < cnt/2){
				ans[i] = 1;
			}
			else ans[i] = 0;
			ct++;
		}
	}
	*/
	cout<<'!'<<' ';
	f0r(i,n){
		if(ans[i])cout<<')';
		else cout<<'(';
	}
	cout<<endl;
}

• Subtask 1: 14 / 14
• Subtask 2: 7 / 7
• Subtask 3: 57 / 57
• Subtask 4: 22 / 22