oj.uz

Submission #51022

# Submission time Handle Problem Language Result Execution time Memory
51022 2018-06-15T15:46:41 Z SpaimaCarpatilor Match (CEOI16_match) C++17
0 / 100
 2 ms 440 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 440 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 440 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 440 KB Output isn't correct
3 Halted 0 ms 0 KB -