oj.uz

Submission #608814

# Submission time Handle Problem Language Result Execution time Memory
608814 2022-07-27T10:25:10 Z MadokaMagicaFan Match (CEOI16_match) C++14
0 / 100
 0 ms 212 KB 
#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];
        if (u == i) {
            cout << -1 <<endl;
            return;
        }
        /* 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

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -