Submission #44786

#	Time	Username	Problem	Language	Result	Execution time	Memory
44786		bogdan10bos	Match (CEOI16_match)	C++14	37 / 100	2061 ms	13276 KiB

match

#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 (stderr)

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 / 10
• Subtask 2: 27 / 27
• Subtask 3: 0 / 63