Submission #97290

#	Time	Username	Problem	Language	Result	Execution time	Memory
97290		dalgerok	괄호 문자열 (CEOI16_match)	C++14	100 / 100	24 ms	11960 KiB

match

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


const int N = 1e5 + 5;


string s;
int n, a[N][26];
char ans[N];

void rec(int l, int r){
    if(l >= r){
        return;
    }
    int pos = a[r][s[l]];
    if(pos <= l){
        cout << "-1";
        exit(0);
    }
    ans[l] = '(';
    ans[pos] = ')';
    rec(l + 1, pos - 1);
    rec(pos + 1, r);
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> s;
    for(auto &it : s){
        it -= 'a';
    }
    n = (int)s.size();
    memset(a, -1, sizeof(a));
    for(int i = 0; i < n; i++){
        for(int j = 0; j < 26; j++){
            if(s[i] == j){
                a[i][j] = i;
            }
            else if(i - 1 >= 0 && a[i - 1][s[i]] - 1 >= 0){
                a[i][j] = a[a[i - 1][s[i]] - 1][j];
            }
        }
    }
    rec(0, n - 1);
    for(int i = 0; i < n; i++){
        cout << ans[i];
    }
}

Compilation message (stderr)

match.cpp: In function 'void rec(int, int)':
match.cpp:16:24: warning: array subscript has type 'char' [-Wchar-subscripts]
     int pos = a[r][s[l]];
                        ^
match.cpp: In function 'int main()':
match.cpp:40:48: warning: array subscript has type 'char' [-Wchar-subscripts]
             else if(i - 1 >= 0 && a[i - 1][s[i]] - 1 >= 0){
                                                ^
match.cpp:41:42: warning: array subscript has type 'char' [-Wchar-subscripts]
                 a[i][j] = a[a[i - 1][s[i]] - 1][j];
                                          ^

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