Submission #96931

#	Time	Username	Problem	Language	Result	Execution time	Memory
96931		Kastanda	Match (CEOI16_match)	C++11	100 / 100	19 ms	11888 KiB

match

// I do it for the glory
#include<bits/stdc++.h>
using namespace std;
const int N = 100005, SGM = 26;
int n, C[N][SGM];
char A[N], B[N];
void Solve(int l, int r)
{
    if (r <= l)
        return ;
    int opt = C[r - 1][A[l] - 'a'];
    if (opt <= l)
        {printf("-1\n"); exit(0);}
    B[l] = '('; B[opt] = ')';
    Solve(l + 1, opt);
    Solve(opt + 1, r);
}
int main()
{
    scanf("%s", A);
    n = strlen(A);
    memset(C, -1, sizeof(C));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < SGM; j++)
        {
            if (A[i] - 'a' == j)
                C[i][j] = i;
            else if (i > 0 && C[i - 1][A[i] - 'a'] > 0)
                C[i][j] = C[C[i - 1][A[i] - 'a'] - 1][j];
        }
    Solve(0, n);
    return !printf("%s\n", B);
}

Compilation message (stderr)

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

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