Submission #589179

#	Time	Username	Problem	Language	Result	Execution time	Memory
589179		andrei_boaca	Match (CEOI16_match)	C++14	10 / 100	5 ms	9792 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;
stack<char> st;
vector<int> mypoz[31],v;
set<int> par[100005],imp[100005];
map<vector<int>,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;
    }
    for(int i=1;i<=n;i++)
    {
        if(!st.empty()&&st.top()==s[i])
            st.pop();
        else
            st.push(s[i]);
    }
    if(!st.empty())
    {
        cout<<-1;
        return 0;
    }
    sol.resize(n+1);
    v.resize(26);
    int nr=1;
    nrm[v]=nr;
    sum[0]=nr;
    for(int i=1;i<=n;i++)
    {
        int p=s[i]-'a';
        if(i%2==1)
            v[p]++;
        else
            v[p]--;
        if(nrm.count(v)==0)
        {
            nr++;
            nrm[v]=nr;
        }
        sum[i]=nrm[v];
    }
    for(int i=1;i<=n;i++)
        if(sol[i]!=')')
        {
            sol[i]='(';
            int poz=0;
            for(int j=i+1;j<=n;j+=2)
            {
                if(sol[j]==')')
                    break;
                if(j%2!=i%2&&sum[i-1]==sum[j]&&s[i]==s[j])
                    poz=j;
            }
            sol[poz]=')';
        }
    for(int i=1;i<=n;i++)
        cout<<sol[i];
    return 0;
}

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