oj.uz

Submission #640312

# Submission time Handle Problem Language Result Execution time Memory
640312 2022-09-14T08:34:34 Z myde Zagrade (COI20_zagrade) C++17
14 / 100
 753 ms 392 KB 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
typedef long long ll;
// const ll mod = 1e9 + 7;
const ll MAXN = 1e6 + 5;
#define vi vector<int>
#define vll vector<ll>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define fi first
#define sc second
#define gl                      \
  ios_base::sync_with_stdio(0); \
  cin.tie(0);                   \
  cout.tie(0)

string s;
int in;

void ask(int l, int r)
{
  if (l >= r)
    return;
  if (r == l + 1)
  {
    s[l] = '(';
    s[r] = ')';
    return;
  }
  cout << "? " << l + 1 << ' ' << r - 1 << endl;
  cin >> in;
  if (in == 1)
  {
    s[l] = '(';
    s[r] = ')';
    if (l + 1 < r - 1)
      ask(l + 1, r - 1);
  }
  else
  {
    for (int i = l + 1; i < r; i += 2)
    {
      cout << "? " << l << ' ' << i << endl;
      cin >> in;
      if (in == 1)
      {
        s[l] = '(';
        s[i] = ')';
        ask(l + 1, i - 1);
        ask(i + 1, r);
        return;
      }
    }
  }
}

int main()
{
  gl;
  int n, q;
  cin >> n >> q;
  s.resize(n + 1, '.');
  ask(1, n);

  s.erase(s.begin());

  cout << "! " << s << endl;

  return 0;
}

/*
(()()((())))
)()((())
((()))((()))
)))(((

()()()()()
((()))(())

kalau yang (l + 1, r - 1) good, maka l = ( dan r = )
kalau ga ... check untuk range (l, l + 1), (l, l + 3), ...



*/

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 6 ms 208 KB Output is correct
3 Correct 20 ms 208 KB Output is correct
4 Correct 20 ms 208 KB Output is correct
5 Correct 16 ms 208 KB Output is correct
6 Correct 14 ms 208 KB Output is correct
7 Correct 5 ms 208 KB Output is correct
8 Correct 21 ms 208 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB Mismatch at position 1. Expected ), found (
2 Halted 0 ms 0 KB -

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 753 ms 392 KB Output is correct
3 Runtime error 708 ms 392 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB Mismatch at position 1. Expected ), found .
2 Halted 0 ms 0 KB -