oj.uz

Submission #175980

# Submission time Handle Problem Language Result Execution time Memory
175980 2020-01-07T13:04:54 Z Ruxandra985 Match (CEOI16_match) C++14
100 / 100
 33 ms 22136 KB 
#include <bits/stdc++.h>
using namespace std;
int sp[30][100010] , go[30][100010];
char sol[100010] , s[100010];
int ok;
int stk[100010];
int match (int st , int dr){
    int i , elem = 0;
    if (st > dr)
        return 1;
    for (i=0;i<'z' - 'a';++i){
        if (((sp[i][dr] - sp[i][st-1]) & 1) == 1)
            return 0;
    }

    for (i=st;i<=dr;++i){
        if (stk[elem] == s[i])
            elem--;
        else stk[++elem] = s[i];
    }
    return (elem == 0);

}
void solve (int st , int dr){
    int i , small;

    if (st > dr)
        return;
    /// stii ca pe st pui ( , gaseste i match ul
    if (s[st] == s[dr])
        i = dr;
    else i = go[s[st]][dr];

    sol[st] = '(';
    sol[i] = ')';
    solve(st + 1 , i - 1);
    solve (i + 1 , dr);
}
int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int n , i , x;
    fgets (s+1 , 100010 , fin);

    n = 0;
    while ( 'a' <= s[n+1] && s[n+1] <= 'z' ){
        n++;
        s[n]-='a';

        for (i=0;i<='z'-'a';++i){
            sp[i][n] = sp[i][n-1] + (s[n] == i);
        }
    }
    stk[0] = -1;
    if (!match(1 , n)){
        fprintf (fout,"-1");
        return 0;
    }
    for (i = 1; i <= n ; i++){

        if (i-1 && s[i-1] == s[i])
            x = i - 2;
        else x = go[s[i]][i-1] - 1;


        for (int j = 0 ; j <= 'z' - 'a' ; j++){
            if (j == s[x] && x)
                go[j][i] = x;
            else if (x >=0)
                go[j][i] = go[j][ x ];
        }
    }
    ok = 1;
    solve (1 , n);
    fputs (sol+1,fout);
    return 0;
}

Compilation message

match.cpp: In function 'void solve(int, int)':
match.cpp:32:22: warning: array subscript has type 'char' [-Wchar-subscripts]
     else i = go[s[st]][dr];
                      ^
match.cpp:25:13: warning: unused variable 'small' [-Wunused-variable]
     int i , small;
             ^~~~~
match.cpp: In function 'int main()':
match.cpp:64:25: warning: array subscript has type 'char' [-Wchar-subscripts]
         else x = go[s[i]][i-1] - 1;
                         ^
match.cpp:44:11: warning: ignoring return value of 'char* fgets(char*, int, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     fgets (s+1 , 100010 , fin);
     ~~~~~~^~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/stdio.h:936:0,
                 from /usr/include/c++/7/cstdio:42,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:46,
                 from match.cpp:1:
In function 'char* fgets(char*, int, FILE*)',
    inlined from 'int main()' at match.cpp:44:11:
/usr/include/x86_64-linux-gnu/bits/stdio2.h:261:58: warning: call to '__fgets_chk_warn' declared with attribute warning: fgets called with bigger size than length of destination buffer
  return __fgets_chk_warn (__s, __bos (__s), __n, __stream);
                                                          ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 2 ms 632 KB Output is correct
3 Correct 2 ms 504 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 2 ms 632 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 760 KB Output is correct
5 Correct 2 ms 760 KB Output is correct
6 Correct 13 ms 1016 KB Output is correct
7 Correct 3 ms 1016 KB Output is correct

Subtask #3
63.0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 2 ms 632 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 760 KB Output is correct
5 Correct 2 ms 760 KB Output is correct
6 Correct 13 ms 1016 KB Output is correct
7 Correct 3 ms 1016 KB Output is correct
8 Correct 4 ms 1912 KB Output is correct
9 Correct 4 ms 2168 KB Output is correct
10 Correct 4 ms 2040 KB Output is correct
11 Correct 4 ms 2168 KB Output is correct
12 Correct 19 ms 13560 KB Output is correct
13 Correct 21 ms 14588 KB Output is correct
14 Correct 23 ms 15864 KB Output is correct
15 Correct 28 ms 18140 KB Output is correct
16 Correct 20 ms 18168 KB Output is correct
17 Correct 27 ms 19236 KB Output is correct
18 Correct 26 ms 19576 KB Output is correct
19 Correct 31 ms 21112 KB Output is correct
20 Correct 20 ms 13688 KB Output is correct
21 Correct 33 ms 22136 KB Output is correct