Submission #683783

#	Time	Username	Problem	Language	Result	Execution time	Memory
683783		MtSaka	Zagrade (COI20_zagrade)	C++17	100 / 100	934 ms	904 KiB

zagrade

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
bool query(int l,int r){
  cout<<"? "<<l+1<<" "<<r<<endl;
  int res;cin>>res;
  return res;
}
int main(){
  int n,q;cin>>n>>q;
  stack<int>st;
  st.push(0);
  string ans(n,' ');
  for(int i=1;i<n;i++){
    if(st.empty()){
      st.push(i);
      continue;
    }
    auto res=query(st.top(),i+1);
    if(res){
      ans[i]=')';
      ans[st.top()]='(';
      st.pop();
    }
    else st.push(i);
  }
  int cnt=count(ans.begin(),ans.end(),' ');
  int now=0;
  for(int i=0;i<n;i++){
    if(ans[i]==' ')ans[i]=(now++<cnt/2?')':'(');
  }
  cout<<"! "<<ans<<endl;
}

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