Submission #247438

#	Time	Username	Problem	Language	Result	Execution time	Memory
247438		evpipis	Match (CEOI16_match)	C++11	100 / 100	20 ms	12160 KiB

match

#include <bits/stdc++.h>
using namespace std;

const int len = 1e5+5, sig = 26;
char str[len], out[len];
int arr[len], dp[len][sig];
stack<int> mys;

bool check(int n){
    for (int i = 1; i <= n; i++){
        if (!mys.empty() && mys.top() == arr[i])
            mys.pop();
        else
            mys.push(arr[i]);
    }

    return (mys.empty());
}

void solve(int l, int r){
    if (l > r) return;
    int k = dp[r][arr[l]];

    //printf("l = %d, r = %d, k = %d\n", l, r, k);

    out[l] = '(';
    out[k] = ')';

    solve(l+1, k-1);
    solve(k+1, r);
}

int main(){
    scanf("%s", str);
    int n = strlen(str);

    for (int i = 1; i <= n; i++)
        arr[i] = str[i-1]-'a';

    if (!check(n)){
        printf("-1\n");
        return 0;
    }

    for (int i = 1; i <= n; i++){
        int k = dp[i-1][arr[i]];
        if (k > 0)
            for (int j = 0; j < sig; j++)
                dp[i][j] = dp[k-1][j];
        dp[i][arr[i]] = i;
    }

    solve(1, n);

    for (int i = 1; i <= n; i++)
        printf("%c", out[i]);
    printf("\n");
    return 0;
}

Compilation message (stderr)

match.cpp: In function 'int main()':
match.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", str);
     ~~~~~^~~~~~~~~~~

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