oj.uz

답안 #155074

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
155074 2019-09-26T07:19:31 Z lyc 괄호 문자열 (CEOI16_match) C++14
0 / 100
 421 ms 524288 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef pair<ii, int> ri3;
#define mp make_pair
#define pb push_back
#define fi first
#define sc second
#define SZ(x) (int)(x).size()
#define ALL(x) begin(x), end(x) 
#define REP(i, n) for (int i = 0; i < n; ++i) 
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define RFOR(i, a, b) for (int i = a; i >= b; --i)

const int MAXN = 1e5+5;

string S;
int N;
int prevStart[MAXN][26];
queue<int> q[26];
stack<int> stk;

string solve(int a, int b) {
    if (a > b) return "";
    if (a+1 == b) return "()";
    int idx = prevStart[b][S[a]-'a'];
    return '(' + solve(a+1,idx-1) + ')' + solve(idx+1,b);
}

int main() {
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> S;
    N = S.length();
    memset(prevStart, -1, sizeof prevStart);

    FOR(i,0,N-1){
        FOR(j,0,25){
            if (j == S[i]-'a') prevStart[i][j] = i;
            else {
                if (i == 0 or prevStart[i-1][S[i]-'a'] <= 0) prevStart[i][j] = -1;
                else prevStart[i][j] = prevStart[prevStart[i-1][S[i]-'a']-1][j];
            }
        }
    }

    if (!stk.empty()) cout << -1 << '\n';
    else cout << solve(0,N-1) << '\n';
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 10544 KB Output is correct
2 Correct 10 ms 10488 KB Output is correct
3 Runtime error 421 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 10544 KB Output is correct
2 Correct 10 ms 10488 KB Output is correct
3 Runtime error 421 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #3
0 / 63.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 10544 KB Output is correct
2 Correct 10 ms 10488 KB Output is correct
3 Runtime error 421 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)