Submission #609335

#	Time	Username	Problem	Language	Result	Execution time	Memory
609335		Minindu2006	Match (CEOI16_match)	C++14	37 / 100	2086 ms	24908 KiB

match

#include <bits/stdc++.h>
using namespace std;
 
string s, ans;
void findSeq(int l, int r)
{
    if (r - l <= 0)
        return;
    int i;
    stack<char> st;
 
    // End index
    for (i = r; i > l; i--)
    {
        if(s[i] == s[l] && st.empty())
            break;
        if(!st.empty() && st.top() == s[i])
            st.pop();
        else
            st.push(s[i]);
        if(s[i] == s[l] && st.empty())
            break;
    }
    ans[l] = '(', ans[i] = ')';
    findSeq(l + 1, i - 1);
    findSeq(i + 1, r);
}
 
void solve()
{
    cin >> s;
    int n = s.size();
 
    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()
{    
 solve();
}

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 0 / 63