Submission #761772

#	Time	Username	Problem	Language	Result	Execution time	Memory
761772		Tenis0206	Match (CEOI16_match)	C++11	100 / 100	30 ms	62640 KiB

match

#include <bits/stdc++.h>

using namespace std;

const int nmax = 1e5;

string s;
string rez;

int l[nmax + 5][155];

bool ok = true;

void solve(int st, int dr)
{
    if(st > dr)
    {
        return;
    }
    int poz = l[dr][s[st]];
    if(poz==-1 || poz <= st)
    {
        ok = false;
        return;
    }
    rez[st] = '(';
    rez[poz] = ')';
    solve(st+1,poz-1);
    solve(poz+1,dr);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
#ifdef home
    freopen("nr.in","r",stdin);
    freopen("nr.out","w",stdout);
#endif // home
    cin>>s;
    int n = s.size();
    rez.resize(n + 1);
    s = "#" + s;
    for(int c='a';c<='z'; c++)
    {
        l[0][c] = -1;
    }
    for(int i=1;i<=n;i++)
    {
        for(int c='a';c<='z';c++)
        {
            l[i][c] = -1;
        }
        int poz = l[i - 1][s[i]];
        if(s[i - 1] == s[i])
        {
            poz = i - 1;
        }
        l[i][s[i]] = i;
        if(poz == -1)
        {
            continue;
        }
        l[i][s[poz - 1]] = max(l[i][s[poz-1]], poz - 1);
        for(int c='a';c<='z';c++)
        {
            l[i][c] = max(l[i][c], l[poz - 1][c]);
        }
    }
    solve(1,n);
    if(!ok)
    {
        cout<<-1<<'\n';
        return 0;
    }
    for(int i=1; i<=n; i++)
    {
        cout<<rez[i];
    }
    cout<<'\n';
    return 0;
}

Compilation message (stderr)

match.cpp: In function 'void solve(int, int)':
match.cpp:20:26: warning: array subscript has type 'char' [-Wchar-subscripts]
   20 |     int poz = l[dr][s[st]];
      |                          ^
match.cpp: In function 'int main()':
match.cpp:54:32: warning: array subscript has type 'char' [-Wchar-subscripts]
   54 |         int poz = l[i - 1][s[i]];
      |                                ^
match.cpp:59:18: warning: array subscript has type 'char' [-Wchar-subscripts]
   59 |         l[i][s[i]] = i;
      |                  ^
match.cpp:64:24: warning: array subscript has type 'char' [-Wchar-subscripts]
   64 |         l[i][s[poz - 1]] = max(l[i][s[poz-1]], poz - 1);
      |                        ^
match.cpp:64:45: warning: array subscript has type 'char' [-Wchar-subscripts]
   64 |         l[i][s[poz - 1]] = max(l[i][s[poz-1]], poz - 1);
      |                                             ^

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 63 / 63