Submission #51022

#	Time	Username	Problem	Language	Result	Execution time	Memory
51022		SpaimaCarpatilor	Match (CEOI16_match)	C++17	0 / 100	2 ms	440 KiB

match

#include<bits/stdc++.h>

using namespace std;

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

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=N; i>=1; i--)
{
    t[i] = nxt[i + 1][sir[i]];
    nxt[i][sir[i]] = i;
    if (t[i] != 0)
    {
        for (int c=0; c<26; c++)
            if (c != sir[i])
                nxt[i][c] = nxt[t[i] + 1][c];
    }
}
int maybe = t[1];
while (maybe < N && maybe != 0)
    maybe = t[maybe + 1];
if (maybe != N)
{
    printf ("-1\n");
    return 0;
}
for (int i=N; i>=1; i--)
    for (int j=0; j<26; j++)
        if (nxt[i][j] != 0)
        {
            int k = nxt[i + 1][j];
            if (lst[k + 1][j] != 0) lst[i][j] = lst[k + 1][j];
            else lst[i][j] = k;
        }
for (int i=1; i<=N; i++)
    if (ans[i] == 0)
    {
        int j = lst[i][sir[i]];
        ans[i] = '(', ans[j] = ')';
        /*for (int k=1; k<=N; k++)
            if (ans[k] == 0) printf (".");
            else printf ("%c", ans[k]);
        printf ("\n");*/
    }
printf ("%s\n", ans + 1);
return 0;
}

Compilation message (stderr)

match.cpp: In function 'int main()':
match.cpp:18:29: warning: array subscript has type 'char' [-Wchar-subscripts]
     t[i] = nxt[i + 1][sir[i]];
                             ^
match.cpp:19:18: warning: array subscript has type 'char' [-Wchar-subscripts]
     nxt[i][sir[i]] = i;
                  ^
match.cpp:46:30: warning: array subscript has type 'char' [-Wchar-subscripts]
         int j = lst[i][sir[i]];
                              ^
match.cpp:13: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: 0 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 63