oj.uz

Submission #175821

# Submission time Handle Problem Language Result Execution time Memory
175821 2020-01-07T11:23:55 Z Ruxandra985 Match (CEOI16_match) C++14
37 / 100
 2000 ms 8696 KB 
/// oare cat de bine merge in practica?
#include <bits/stdc++.h>
#pragma GCC optimize "Ofast"
using namespace std;
int sp[30][100010];
int match_left[100010] , match_right[100010] , fl[30] , fr[30];
char sol[100010] , s[100010];
int ok;
int stk_l[100010] , stk_r[100010];
void match (int st , int dr){
    int i , elem_l = 0 , elem_r = 0 , poz;
    /// build match_left si match_right
    /// match_left[i] = match (st ... i)
    /// match_right[i] = match (i ... dr)
    match_left[st - 1] = match_right[dr + 1] = 1;
    for (i = 0 ; i < dr - st + 1 ; i++){

        poz = i + st; /// calc match_left[poz]
        if (stk_l[elem_l] == s[poz])
            elem_l--;
        else stk_l[++elem_l] = s[poz];
        if (!elem_l)
            match_left[poz] = 1;
        else match_left[poz] = 0;

        poz = dr - i; /// calc match_right[poz]
        if (stk_r[elem_r] == s[poz])
            elem_r--;
        else stk_r[++elem_r] = s[poz];
        if (!elem_r)
            match_right[poz] = 1;
        else match_right[poz] = 0;
    }

}
void solve (int st , int dr){
    int i;
    if (st > dr)
        return;
    if (!ok) /// nu mai are rost
        return;
    /// stii ca pe st pui ( , gaseste i match ul
    match(st + 1 , dr);
    for (i = ( ( (dr & 1) != (st & 1) ) ? dr : dr - 1); i >= st + 1 ; i-=2){
        if (match_left[i - 1] && match_right[i + 1])
            break;
    }
    if (i < st + 1){
        ok = 0;
        return;
    }
    else {
        sol[st] = '(';
        sol[i] = ')';
        solve(st + 1 , i - 1);
        solve (i + 1 , dr);
    }
}
int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int n , i;
    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_l[0] = stk_r[0] = -1;
    ok = 1;
    solve (1 , n);
    if (ok == 0){
        fprintf (fout,"%d\n",-1);
    }
    else {
        fputs (sol+1,fout);
    }
    return 0;
}

Compilation message

match.cpp: In function 'int main()':
match.cpp:64: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:2:
In function 'char* fgets(char*, int, FILE*)',
    inlined from 'int main()' at match.cpp:64: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 3 ms 504 KB Output is correct
2 Correct 3 ms 504 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 3 ms 504 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 3 ms 632 KB Output is correct
5 Correct 3 ms 632 KB Output is correct
6 Correct 6 ms 632 KB Output is correct
7 Correct 6 ms 760 KB Output is correct

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 3 ms 632 KB Output is correct
5 Correct 3 ms 632 KB Output is correct
6 Correct 6 ms 632 KB Output is correct
7 Correct 6 ms 760 KB Output is correct
8 Correct 12 ms 1144 KB Output is correct
9 Correct 88 ms 1400 KB Output is correct
10 Correct 48 ms 1400 KB Output is correct
11 Correct 64 ms 1400 KB Output is correct
12 Execution timed out 2040 ms 8696 KB Time limit exceeded
13 Halted 0 ms 0 KB -