Submission #640312

#	Time	Username	Problem	Language	Result	Execution time	Memory
640312		myde	Zagrade (COI20_zagrade)	C++17	14 / 100	753 ms	392 KiB

zagrade

#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 / 14
• Subtask 2: 0 / 7
• Subtask 3: 0 / 57
• Subtask 4: 0 / 22