oj.uz

Submission #608902

# Submission time Handle Problem Language Result Execution time Memory
608902 2022-07-27T11:06:14 Z generic_placeholder_name Match (CEOI16_match) C++17
37 / 100
 2000 ms 484 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 4 ms 324 KB Output is correct
5 Correct 4 ms 212 KB Output is correct
6 Correct 8 ms 212 KB Output is correct
7 Correct 16 ms 328 KB Output is correct

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 4 ms 324 KB Output is correct
5 Correct 4 ms 212 KB Output is correct
6 Correct 8 ms 212 KB Output is correct
7 Correct 16 ms 328 KB Output is correct
8 Correct 152 ms 320 KB Output is correct
9 Correct 138 ms 320 KB Output is correct
10 Correct 97 ms 340 KB Output is correct
11 Correct 70 ms 328 KB Output is correct
12 Execution timed out 2084 ms 484 KB Time limit exceeded
13 Halted 0 ms 0 KB -