제출 #1262734

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1262734		biank	Match (CEOI16_match)	C++20	100 / 100	15 ms	15428 KiB

match

#include <bits/stdc++.h>
 
using namespace std;
 
#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)
 
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
 
using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using ii = pair<int, int>;
using vii = vector<ii>;
 
#define fst first
#define snd second
 
#define pb push_back
#define eb emplace_back
 
void solve(int l, int r, const vector<vi> &match, string &ret, const string &s) {
    if (l > r) return;
    int m = match[r][s[l] - 'a'];
    ret[l] = '(', ret[m] = ')';
    solve(l + 1, m - 1, match, ret, s);
    solve(m + 1, r, match, ret, s);
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    string s;
    cin >> s;
    const int n = sz(s);
    auto check = [&](string pending = "#") {
        forn(i, n) {
            if (pending.back() == s[i]) {
                pending.pop_back();
            } else {
                pending += s[i];
            }
        }
        return pending == "#";
    };
    if (!check()) {
        cout << "-1\n";
        return 0;
    }
    vector<vi> match(n, vi(26));
    forn(i, n) forn(j, 26) {
        if (s[i] - 'a' == j) {
            match[i][j] = i;
        } else if (i > 0 && match[i - 1][s[i] - 'a'] > 0) {
            match[i][j] = match[match[i - 1][s[i] - 'a'] - 1][j];
        }
        
    }
    string ret(n, '?');
    solve(0, n - 1, match, ret, s);
    cout << ret << '\n';
    
    return 0;
}

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