#pragma GCC optimize("O3")
#pragma GCC target("sse4")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
#define FOR(i, a, b) for (int i = a; i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define FORd(i, a, b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i, a) for (int i = (a)-1; i >= 0; i--)
#define trav(a, x) for (auto &a : x)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
#define len(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define fst first
#define nl endl
#define sec second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define ins insert
const int MOD = 1000000007;
const int MX = INT_MAX;
const int MN = INT_MIN;
void init()
{
#ifndef ONLINE_JUDGE
freopen("input.in", "r", stdin);
freopen("output.out", "w", stdout);
#endif
}
void fastIO()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
}
string s, ans;
void findSeq(int l, int r)
{
if (r - l <= 0)
return;
int i;
char cur = s[l];
stack<char> st;
// End index
for (i = r; i > l; i--)
{
if(s[i] == cur && st.empty())
break;
if(!st.empty() && st.top() == s[i])
st.pop();
else
st.push(s[i]);
if(s[i] == cur && st.empty())
break;
}
ans[l] = '(', ans[i] = ')';
findSeq(l + 1, i - 1);
findSeq(i + 1, r);
}
void solve()
{
cin >> s;
int n = len(s);
if (n % 2)
{
cout << -1;
return;
}
// Is it possible to create a bracket sequence
stack<char> st;
for (int i = 0; i < n; i++)
{
if (!st.empty() && st.top() == s[i])
st.pop();
else
st.push(s[i]);
}
if (!st.empty())
{
cout << -1;
return;
}
ans.resize(n, 'X');
findSeq(0, n - 1);
cout << ans;
}
int main()
{
fastIO();
init();
int t = 1;
// cin >> t;
while (t--)
solve();
return 0;
}
Compilation message
match.cpp: In function 'void init()':
match.cpp:38:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
38 | freopen("input.in", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
match.cpp:39:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
39 | freopen("output.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
