Submission #608849

#	Time	Username	Problem	Language	Result	Execution time	Memory
608849		generic_placeholder_name	Match (CEOI16_match)	C++17	0 / 100	0 ms	212 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();
    ordered_set<int> lf;
    rep(i, n) lf.insert(i);
    vector<char> ans(n);
    while(!s.empty()) {
        int l = 0, r;
        bool ok = 0;
        for(int i = 1; i <= s.size(); i++) {
            if(i == s.size() || s[i] != s[i - 1]) {
                r = i - 1;
                if((r - l) & 1) {
                    int len = r - l + 1;
                    rep(_, len / 2) {
                        int v = *lf.find_by_order(l);
                        ans[v] = '(';
                        lf.erase(v);
                    }
                    rep(_, len / 2) {
                        int v = *lf.find_by_order(l);
                        ans[v] = ')';
                        lf.erase(v);
                    }
                    string nw;
                    rep(i, s.size()) if(i < l || i > r) nw.pb(s[i]);
                    s = move(nw);
                    ok = 1;
                    break;
                }
                else l = i;
            }
        }
        if(!ok) return cout << "-1\n", 0;
    }
    rep(i, n) cout << ans[i]; cout << endl;
}

Compilation message (stderr)

match.cpp: In function 'int32_t main()':
match.cpp:55:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         for(int i = 1; i <= s.size(); i++) {
      |                        ~~^~~~~~~~~~~
match.cpp:56:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |             if(i == s.size() || s[i] != s[i - 1]) {
      |                ~~^~~~~~~~~~~
match.cpp:23:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 | #define rep(i, n) for (int i=0; i<(n); i++)
      |                                  ^
match.cpp:71:21: note: in expansion of macro 'rep'
   71 |                     rep(i, s.size()) if(i < l || i > r) nw.pb(s[i]);
      |                     ^~~
match.cpp:23:19: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   23 | #define rep(i, n) for (int i=0; i<(n); i++)
      |                   ^~~
match.cpp:81:5: note: in expansion of macro 'rep'
   81 |     rep(i, n) cout << ans[i]; cout << endl;
      |     ^~~
match.cpp:81:31: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   81 |     rep(i, n) cout << ans[i]; cout << endl;
      |                               ^~~~

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