Submission #51027

#	Time	Username	Problem	Language	Result	Execution time	Memory
51027		SpaimaCarpatilor	Match (CEOI16_match)	C++17	100 / 100	20 ms	13536 KiB

match

#include<bits/stdc++.h>

using namespace std;

int N, t[100009], prv[100009][26];
char sir[100009], ans[100009];

void solve (int i, int j)
{
    if (i > j) return ;
    int k = (sir[j] == sir[i] ? j : prv[j][sir[i]]);
    ans[i] = '(', ans[k] = ')';
/*    for (int k=1; k<=N; k++)
        if (ans[k] == 0) printf (".");
        else printf ("%c", ans[k]);
    printf ("\n");*/
    solve (i + 1, k - 1);
    solve (k + 1, j);
}

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

scanf ("%s", sir + 1), N = strlen (sir + 1);
for (int i=1; i<=N; i++)
    sir[i] -= 'a';
for (int i=1; i<=N; i++)
{
    if (i > 1 && sir[i - 1] == sir[i]) t[i] = i - 1;
    else t[i] = prv[i - 1][sir[i]];
    if (t[i] != 0)
    {
        int forbC = sir[t[i] - 1];
        if (t[i] == 1) forbC = -1;
        else prv[i][forbC] = t[i] - 1;
        for (int c=0; c<26; c++)
            if (c != forbC)
                prv[i][c] = prv[t[i] - 1][c];
    }
}
int maybe = t[N];
while (maybe > 1 && maybe != 0)
    maybe = t[maybe - 1];
if (maybe != 1)
{
    printf ("-1\n");
    return 0;
}
solve (1, N);
printf ("%s\n", ans + 1);
return 0;
}

Compilation message (stderr)

match.cpp: In function 'void solve(int, int)':
match.cpp:11:50: warning: array subscript has type 'char' [-Wchar-subscripts]
     int k = (sir[j] == sir[i] ? j : prv[j][sir[i]]);
                                                  ^
match.cpp: In function 'int main()':
match.cpp:32:34: warning: array subscript has type 'char' [-Wchar-subscripts]
     else t[i] = prv[i - 1][sir[i]];
                                  ^
match.cpp:26:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf ("%s", sir + 1), N = strlen (sir + 1);
 ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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