제출 #681415

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
681415		vjudge1	괄호 문자열 (CEOI16_match)	C++14	100 / 100	29 ms	50360 KiB

match

#include <bits/stdc++.h>
using namespace std;
 
#define F first
#define S second
#define pb push_back
#define all(a) a.begin(), a.end()
 
typedef long long ll;
typedef pair<int, int> ii;
 
const int N = 1e5 + 5;
const int mod = 1e9 + 7;

int lst[N]['z' + 1];
string s;
string t;
int n;
 
void rec(int l, int r)
{
    if(l > r) return;
    int mid = lst[r][s[l]];
    
    // assert(mid >= 0);
    
    t[l] = '(', t[mid] = ')';
    rec(l + 1, mid - 1);
    rec(mid + 1, r);
}
 
void solve()
{
    cin >> s;
    int n = s.size();
    t.resize(n);
    
    stack<char> st;
    for(int i = 0; i < n; i++)
    {
        if(st.size())
        {
            if(st.top() == s[i])
                st.pop();
            else
                st.push(s[i]);
        } else st.push(s[i]);
    }
    if(st.size()) cout << -1, exit(0);
    
    for(int i = 0; i < n; i++)
    {
        lst[i][s[i]] = i;
        if(i == 0) continue;
        
        int j = lst[i - 1][s[i]];
        for(char c = 'a'; c <= 'z'; c++)
            if(j > 0 && c != s[i]) lst[i][c] = lst[j - 1][c];
    }
    rec(0, n - 1);
    cout << t;
}
 
signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    // cin >> t;
    while(t--) solve();
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

match.cpp: In function 'void rec(int, int)':
match.cpp:23:26: warning: array subscript has type 'char' [-Wchar-subscripts]
   23 |     int mid = lst[r][s[l]];
      |                          ^
match.cpp: In function 'void solve()':
match.cpp:53:20: warning: array subscript has type 'char' [-Wchar-subscripts]
   53 |         lst[i][s[i]] = i;
      |                    ^
match.cpp:56:32: warning: array subscript has type 'char' [-Wchar-subscripts]
   56 |         int j = lst[i - 1][s[i]];
      |                                ^
match.cpp:58:43: warning: array subscript has type 'char' [-Wchar-subscripts]
   58 |             if(j > 0 && c != s[i]) lst[i][c] = lst[j - 1][c];
      |                                           ^
match.cpp:58:59: warning: array subscript has type 'char' [-Wchar-subscripts]
   58 |             if(j > 0 && c != s[i]) lst[i][c] = lst[j - 1][c];
      |                                                           ^

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