Submission #589193

#	Time	Username	Problem	Language	Result	Execution time	Memory
589193		andrei_boaca	괄호 문자열 (CEOI16_match)	C++14	37 / 100	2088 ms	42156 KiB

match

#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
int n;
string s,sol;
vector<char> st;
vector<int> mypoz[31],v;
set<int> par[100005],imp[100005];
map<vector<char>,int> nrm;
int nxt[100005];
int sum[100005];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>s;
    n=s.size();
    s=" "+s;
    if(n%2==1)
    {
        cout<<-1;
        return 0;
    }
    int nr=1;
    nrm[st]=1;
    sum[0]=1;
    for(int i=1;i<=n;i++)
    {
        if(!st.empty()&&st.back()==s[i])
            st.pop_back();
        else
            st.push_back(s[i]);
        if(nrm[st]==0)
        {
            nr++;
            nrm[st]=nr;
        }
        sum[i]=nrm[st];
        /*if(st.empty())
            cout<<'-';
        for(char j:st)
            cout<<j<<' ';
        cout<<'\n';*/
    }
    if(!st.empty())
    {
        cout<<-1;
        return 0;
    }
    sol.resize(n+1);
    for(int i=1;i<=n;i++)
        if(sol[i]!=')')
    {
        sol[i]='(';
        int poz=0;
        for(int j=i+1;j<=n;j++)
        {
            if(sol[j]==')')
                break;
            if(j%2!=i%2&&s[j]==s[i]&&sum[i-1]==sum[j])
                poz=j;
        }
        sol[poz]=')';
    }
    for(int i=1;i<=n;i++)
        cout<<sol[i];
    return 0;
}

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