oj.uz

Submission #44786

# Submission time Handle Problem Language Result Execution time Memory
44786 2018-04-06T12:06:24 Z bogdan10bos Match (CEOI16_match) C++14
37 / 100
 2000 ms 13276 KB 
#include <bits/stdc++.h>

using namespace std;

//#define FILE_IO

int N;
int lft[100005], rgt[100005];
char s[100005], r[100005];

void solve(int st, int dr)
{
    if(st + 1 == dr)
    {
        r[st] = '(';
        r[dr] = ')';
        return;
    }
    if( (dr - st + 1) <= 2 ) return;

    stack<char> stv;
    for(int i = st; i <= dr; i++)   lft[i] = 0;
    for(int i = st + 1; i <= dr; i++)
    {
        if(stv.empty() || stv.top() != s[i])
            stv.push(s[i]);
        else
            stv.pop();

        if(stv.empty()) lft[i] = 1;
    }

    while(!stv.empty()) stv.pop();
    for(int i = st; i <= dr; i++)   rgt[i] = 0;
    for(int i = dr; i >= st; i--)
    {
        if(stv.empty() || stv.top() != s[i])
            stv.push(s[i]);
        else
            stv.pop();

        if(stv.empty()) rgt[i] = 1;
    }

    lft[st] = 1;
    rgt[dr + 1] = 1;
    int pos = 0;
    for(int i = dr; i > st; i--)
        if(s[i] == s[st] && lft[i - 1] && rgt[i + 1])
        {
            pos = i;
            break;
        }
    if(pos == 0)
    {
        printf("-1\n");
        exit(0);
    }

    r[st] = '(';
    r[pos] = ')';

    solve(st + 1, pos - 1);
    solve(pos + 1, dr);
}

int main()
{
    #ifdef FILE_IO
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
    #endif

    scanf("%s", s + 1);
    N = strlen(s + 1);

    solve(1, N);

    printf("%s\n", r + 1);

    return 0;
}

Compilation message

match.cpp: In function 'int main()':
match.cpp:74:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", s + 1);
     ~~~~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 360 KB Output is correct
3 Correct 2 ms 600 KB Output is correct
4 Correct 2 ms 668 KB Output is correct
5 Correct 3 ms 672 KB Output is correct
6 Correct 8 ms 1096 KB Output is correct
7 Correct 6 ms 1096 KB Output is correct

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 360 KB Output is correct
3 Correct 2 ms 600 KB Output is correct
4 Correct 2 ms 668 KB Output is correct
5 Correct 3 ms 672 KB Output is correct
6 Correct 8 ms 1096 KB Output is correct
7 Correct 6 ms 1096 KB Output is correct
8 Correct 11 ms 1096 KB Output is correct
9 Correct 95 ms 2340 KB Output is correct
10 Correct 47 ms 2340 KB Output is correct
11 Correct 77 ms 3052 KB Output is correct
12 Execution timed out 2061 ms 13276 KB Time limit exceeded
13 Halted 0 ms 0 KB -