Submission #154378

#	Time	Username	Problem	Language	Result	Execution time	Memory
154378		arnold518	Match (CEOI16_match)	C++14	100 / 100	22 ms	13308 KiB

match

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;

int N;
char S[MAXN+10], ans[MAXN+10];
int P[MAXN+10][30];

void solve(int l, int r)
{
    if(r<l) return;
    int t=P[r][S[l]-'a'];
    ans[l]='('; ans[t]=')';
    solve(l+1, t-1);
    solve(t+1, r);
}

int main()
{
    int i, j;

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

    vector<char> V;
    for(i=1; i<=N; i++)
    {
        if(!V.empty() && S[i]==V.back()) V.pop_back();
        else V.push_back(S[i]);
    }
    if(!V.empty()) return !printf("-1");

    for(j=0; j<26; j++) P[0][j]=1;
    for(i=1; i<=N; i++)
    {
        for(j=0; j<26; j++)
        {
            if('a'+j==S[i]) P[i][j]=i;
            else P[i][j]=P[P[i-1][S[i]-'a']-1][j];
        }
    }

    solve(1, N);
    printf("%s", ans+1);
}

Compilation message (stderr)

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

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