Submission #608902

#	Time	Username	Problem	Language	Result	Execution time	Memory
608902		generic_placeholder_name	Match (CEOI16_match)	C++17	37 / 100	2084 ms	484 KiB

match

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma,popcnt")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#include <ext/rope>

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define gcd __gcd
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define rep(i, n) for (int i=0; i<(n); i++)
#define rep1(i, n) for (int i=1; i<=(n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define endl "\n"

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned uint;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
template<typename T, typename cmp = less<T>>
using ordered_set = tree<T, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
typedef trie<string, null_type, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update> pref_trie;

int32_t main() {
    fastio;
    string s; cin >> s;
    int n = s.size();
    auto valid = [&](stack<char> st, int i) {
        for(int j = i; j < n; j++) {
            if(!st.empty() && st.top() == s[j]) st.pop();
            else st.push(s[j]);
        }
        return st.empty();
    };
    vector<char> ans(n);
    stack<char> st;
    if(!valid(st, 0)) return puts("-1"), 0;
    rep(i, n) {
        if(!st.empty() && st.top() == s[i]) {
            st.push(s[i]);
            if(valid(st, i + 1)) ans[i] = '(';
            else ans[i] = ')', st.pop(), st.pop();
        }
        else st.push(s[i]), ans[i] = '(';
    }
    rep(i, n) cout << ans[i];
}

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