oj.uz

Submission #175763

# Submission time Handle Problem Language Result Execution time Memory
175763 2020-01-07T10:49:57 Z Ruxandra985 Match (CEOI16_match) C++14
37 / 100
 2000 ms 9460 KB 
/// oare cat de bine merge in practica?
#include <bits/stdc++.h>

using namespace std;
int s[100010] , sp[100010][30];
char sol[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[dr][i] - sp[st-1][i]) & 1) == 1)
            return 0;
    }

    for (i=st;i<=dr;i++){
        if (elem && stk[elem] == s[i])
            elem--;
        else stk[++elem] = s[i];
    }
    return (elem == 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

    for (i = ( ( (dr & 1) != (st & 1) ) ? dr : dr - 1); i >= st + 1 ; i-=2){
        if (match(st + 1 , i - 1) && match(i + 1 , dr))
            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;
    char c;
    c=fgetc(fin);
    n = 0;
    while ( 'a' <= c && c <= 'z' ){
        s[++n] = c-'a';

        for (i=0;i<='z'-'a';i++){
            sp[n][i] = sp[n-1][i] + (s[n] == i);
        }

        c=fgetc(fin);
    }
    ok = 1;
    solve (1 , n);
    if (ok == 0){
        fprintf (fout,"%d\n",-1);
    }
    else {
        for (i=1;i<=n;i++)
            fputc(sol[i],fout);
    }
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 5 ms 632 KB Output is correct
7 Correct 8 ms 656 KB Output is correct

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 5 ms 632 KB Output is correct
7 Correct 8 ms 656 KB Output is correct
8 Correct 22 ms 1144 KB Output is correct
9 Correct 246 ms 1376 KB Output is correct
10 Correct 18 ms 1272 KB Output is correct
11 Correct 25 ms 1400 KB Output is correct
12 Correct 1139 ms 8696 KB Output is correct
13 Correct 1166 ms 9336 KB Output is correct
14 Execution timed out 2073 ms 9460 KB Time limit exceeded
15 Halted 0 ms 0 KB -