제출 #810478

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

match

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

const int mxN = 1e5 + 10;

int n;
string s;

namespace sub {
    int mark[mxN];
    
    bool check() {
        vector<int> q;
        
        for(int i = 1; i <= n; i ++) {
            if(mark[i]) {
                q.push_back(i - 1);
                continue ;
            }    
            
            if(!q.empty() && s[q.back()] == s[i - 1]) q.pop_back();
            else {
                q.push_back(i - 1);
            }
        }
        
        return q.size() == 0;
    }
    
    int main() {
        for(int i = 1; i <= n; i ++) mark[i] = 0;
        
        if(!check()) {
            return cout << -1, 0;
        }
        
        for(int i = 1; i <= n; i ++) {
            mark[i] = 1;
            mark[i] = check();
        }
            
        for(int i = 1; i <= n; i ++) cout << (mark[i] ? '(' : ')');
        return 0;
    }   
}

namespace full {
    
    struct trie {
        struct node {
            int child[26];
            int num[26];
        };
        
        vector<node> tree;
        
        void new_node() {
            node nw;
            
            for(int i = 0; i < 26; i ++) {
                nw.child[i] = -1;
                nw.num[i] = -1;
            }
            
            tree.push_back(nw);
        }
        
        void upd(int idx, int i) {
            tree[idx].num[s[i - 1] - 'a'] = i;
        }
        
        int add(int idx, int i) {
            if(tree[idx].child[s[i - 1] - 'a'] == -1) {
                new_node();
                tree[idx].child[s[i - 1] - 'a'] = (int) tree.size() - 1;
            }
            
            idx = tree[idx].child[s[i - 1] - 'a'];
            return idx;
        }
        
        int get(int idx, char ch) {
            return tree[idx].num[ch - 'a'];
        }
    } T;
    
    int prev[mxN][26];
    int f[mxN];
    
    void init() {
        T.new_node();
        vector<pair<int, int>> q;
        
        for(int i = 1; i <= n; i ++) {
            if(!q.empty() && s[q.back().first] == s[i - 1]) {
                q.pop_back();
            } else {
                int idx = T.add((q.size() > 0 ? q.back().second : 0), i);
                q.push_back({i - 1, idx});
            }
            
            T.upd((q.size() > 0 ? q.back().second : 0), i);
            for(char ch = 'a'; ch <= 'z'; ch ++) prev[i][ch - 'a'] = T.get((q.size() > 0 ? q.back().second : 0), ch);
            
            f[i] = (int) q.size();
        }
    }
    
    string dq(int l, int r) {
        if(l > r) return "";
        int m = prev[r][s[l - 1] - 'a'];
        
        return '(' + dq(l + 1, m - 1) + ')' + dq(m + 1, r);
    }
    
    int main() {
        init();
        
        if(f[n]) {
            return cout << -1, 0;
        }
        
        //for(int i = 1; i <= n; i ++) 
        //for(char ch = 'a'; ch <= 'z'; ch ++) 
        //cout << prev[i][ch - 'a'] << " \n"[ch == 'z'];
        
        cout << dq(1, n);
        return 0;
    }
}

int main() {

    cin.tie(0)->sync_with_stdio(0);
    
    cin >> s;
    n = s.size();
    
    //if(n <= 2000) sub :: main(); else 
    full :: main();
    
    return 0;
}

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