Submission #608810

#	Time	Username	Problem	Language	Result	Execution time	Memory
608810		MadokaMagicaFan	괄호 문자열 (CEOI16_match)	C++14	0 / 100	1 ms	468 KiB

match

#include "bits/stdc++.h"

using namespace std;

using ll = long long;
const ll inf = 1e9;
const int md1 = 1e9+7;
const int md2 = 998244353;

#define sz(v)                       ((int)v.size())
#define pb                          push_back

#define pry                         cout << "YES\n"
#define prn                         cout << "NO\n"
#define endl                        '\n'

#define fst                         first
#define scn                         second
#define ONPC

const int N = 1e5;
const int K = 20;

int p[N][K];

int lval[N][26];


#ifdef ONPC
void
solve()
{
    string s;
    int n;
    vector<int> t;
    cin >> s;
    n = sz(s);
    t.assign(n,0);

    if (n&1) {
        cout << "-1\n";
        return;
    }


    for (int i = 0; i < n; ++i) {
        t[i] = (s[i]-'a');
    }

    for (int i = 0; i < n; ++i)
        for (int j = 0; j < 26; ++j)
            lval[i][j] = -1;

    stack<int> st;

    for (int i = 0; i < n; ++i) {
        if (sz(st)) {
            if (st.top() == t[i]) {
                st.pop();
                assert(lval[sz(st)][t[i]]>-1);
                p[lval[sz(st)][t[i]]][0] = i;
                lval[sz(st)][t[i]] = i;
                continue;
            }
        }

        if(lval[sz(st)][t[i]]>-1)
            p[lval[sz(st)][t[i]]][0] = i;
        lval[sz(st)][t[i]] = i;
        st.push(t[i]);
    }

    if (sz(st)) {
        cout << "-1\n";
        return;
    }

    for (int i = 0; i < n; ++i)
        for (int j = 0; j < 26; ++j)
            if (lval[i][j]>-1)
                p[lval[i][j]][0] = i;

    for (int j = 1; j < K; ++j)
        for (int i = 0; i < n; ++i)
            p[i][j] = p[p[i][j-1]][j-1];

    string ans(n, ')');
    st.push(n);
    int limit;
    for (int i = 0; i < n; ++i) {
        if (i == st.top()) {
            st.pop();
            continue;
        }
        ans[i] = '(';
        limit = st.top();
        int u = i;

        for (int j = K-1; j >= 0; --j)
            if (p[u][j] < limit) u = p[u][j];
        assert(u > i);
        st.push(u);
    }

    cout << ans << endl;
}

int32_t
main(int argc, char **argv)
{
    if (argc >= 2) {
        freopen(argv[1], "r", stdin);
    } else
        ios_base::sync_with_stdio(0);cin.tie(0);
    int t = 1;
    /* cin >> t; */
    while(t--)
        solve();
}
#endif

Compilation message (stderr)

match.cpp: In function 'int32_t main(int, char**)':
match.cpp:113:7: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
  113 |     } else
      |       ^~~~
match.cpp:114:38: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
  114 |         ios_base::sync_with_stdio(0);cin.tie(0);
      |                                      ^~~
match.cpp:112:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |         freopen(argv[1], "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

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