oj.uz

답안 #154375

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
154375 2019-09-21T12:14:15 Z arnold518 괄호 문자열 (CEOI16_match) C++14
10 / 100
 29 ms 24312 KB 
#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");

    memset(P, -1, sizeof(P));
    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

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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 12024 KB Output is correct
2 Correct 12 ms 12024 KB Output is correct
3 Correct 2 ms 380 KB Output is correct

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 12024 KB Output is correct
2 Correct 12 ms 12024 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Runtime error 29 ms 24312 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 12024 KB Output is correct
2 Correct 12 ms 12024 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Runtime error 29 ms 24312 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -