Submission #745457

#	Time	Username	Problem	Language	Result	Execution time	Memory
745457		alexdumitru	Match (CEOI16_match)	C++14	10 / 100	1 ms	340 KiB

match

#include <bits/stdc++.h>

using namespace std;

ifstream fin("match.in");
ofstream fout("match.out");

const int NMAX = 100005;

string s;
int n;
int a[NMAX];
int sir[NMAX];
int dp[26][NMAX];

void divide(int st, int dr)
{
    if(st > dr)
        return;
    int pos = dp[a[st]][dr];
    sir[st] = 1;
    sir[pos] = -1;
    divide(st + 1, pos - 1);
    divide(pos + 1, dr);
}

void solve()
{
    cin >> s;
    n = s.length();
    for(int i = 0; i < n; i++)
        a[i + 1] = s[i] - 'a';
    stack<int> st;
    for(int i = 1; i <= n; i++)
    {
        if(!st.empty() && st.top() == a[i])
            st.pop();
        else {
            st.push(a[i]);
        }
    }
    if(!st.empty())
    {
        cout << -1 << '\n';
        return;
    }
    for(int i = 1; i <= n; i++)
    {
        dp[a[i]][i] = i;
        if(i > 1)
        {
            for(int j = 0; j < 26; j++)
                if(j != a[i] && dp[j][i - 1])
                    dp[j][i] = dp[j][dp[j][i - 1]];
        }
    }
    divide(1, n);
    for(int i = 1; i <= n; i++)
    {
        if(sir[i] == 1)
            cout << '(';
        else cout << ')';
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

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