oj.uz

Submission #706432

# Submission time Handle Problem Language Result Execution time Memory
706432 2023-03-06T14:49:26 Z vjudge1 Zagrade (COI20_zagrade) C++17
100 / 100
 985 ms 10248 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod = 1e9 + 7;
const ll mxN = 5e5;
int n,q;
set<int>bf;
set<int>ind;
int main(){
  cin >>n>>q;
  int rem = n;
  char s[mxN];
  for(int i =1 ;i <= n;i++) {bf.insert(i);ind.insert(i - 1);}
  for(int i = 2;i <= n;i++){
    auto x = bf.lower_bound(i);
    if(x == bf.begin()) i++;
    x = bf.lower_bound(i);
    x--;
    int j  = *x;
    cout.flush()<<"? "<<j<<' '<<i<<endl;
    bool cr;
    cin>>cr;
    // for(auto x : bf){
    //   cout<<x<<' ';
    // }
    // cout<<endl;
    if(cr == 1){
      bf.erase(i);
      bf.erase(j);
      ind.erase(i - 1);
      ind.erase(j - 1);
      s[i - 1] = ')';
      s[j - 1] = '(';
      rem -= 2;
    }
  }
  int cnt = 0;
  for(auto x : ind){
    cnt++;
    if(cnt > rem / 2) s[x] = '(';
    else s[x] = ')';
  }
  cout.flush()<<"! "<<s<<endl;
}

Subtask #1
14.0 / 14.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 720 KB Output is correct
2 Correct 10 ms 848 KB Output is correct
3 Correct 7 ms 848 KB Output is correct
4 Correct 8 ms 848 KB Output is correct
5 Correct 8 ms 848 KB Output is correct
6 Correct 9 ms 848 KB Output is correct
7 Correct 9 ms 848 KB Output is correct
8 Correct 8 ms 848 KB Output is correct

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 720 KB Output is correct
2 Correct 403 ms 10160 KB Output is correct
3 Correct 848 ms 10176 KB Output is correct
4 Correct 931 ms 10184 KB Output is correct
5 Correct 910 ms 10160 KB Output is correct
6 Correct 733 ms 10160 KB Output is correct
7 Correct 799 ms 10184 KB Output is correct
8 Correct 893 ms 10176 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 720 KB Output is correct
2 Correct 670 ms 10160 KB Output is correct
3 Correct 697 ms 10156 KB Output is correct
4 Correct 689 ms 10248 KB Output is correct
5 Correct 985 ms 10156 KB Output is correct
6 Correct 626 ms 10164 KB Output is correct
7 Correct 928 ms 10152 KB Output is correct
8 Correct 968 ms 10148 KB Output is correct