oj.uz

Submission #683783

# Submission time Handle Problem Language Result Execution time Memory
683783 2023-01-19T10:55:49 Z MtSaka Zagrade (COI20_zagrade) C++17
100 / 100
 934 ms 904 KB 
#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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 292 KB Output is correct
2 Correct 5 ms 208 KB Output is correct
3 Correct 8 ms 208 KB Output is correct
4 Correct 8 ms 208 KB Output is correct
5 Correct 9 ms 208 KB Output is correct
6 Correct 8 ms 208 KB Output is correct
7 Correct 9 ms 208 KB Output is correct
8 Correct 9 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 7 ms 208 KB Output is correct
3 Correct 11 ms 300 KB Output is correct
4 Correct 10 ms 208 KB Output is correct
5 Correct 7 ms 208 KB Output is correct
6 Correct 10 ms 208 KB Output is correct
7 Correct 9 ms 208 KB Output is correct
8 Correct 9 ms 208 KB Output is correct

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 433 ms 384 KB Output is correct
3 Correct 855 ms 444 KB Output is correct
4 Correct 688 ms 384 KB Output is correct
5 Correct 518 ms 456 KB Output is correct
6 Correct 822 ms 376 KB Output is correct
7 Correct 737 ms 648 KB Output is correct
8 Correct 823 ms 376 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 823 ms 904 KB Output is correct
3 Correct 571 ms 532 KB Output is correct
4 Correct 792 ms 632 KB Output is correct
5 Correct 588 ms 448 KB Output is correct
6 Correct 769 ms 588 KB Output is correct
7 Correct 598 ms 596 KB Output is correct
8 Correct 934 ms 384 KB Output is correct