oj.uz

Submission #608832

# Submission time Handle Problem Language Result Execution time Memory
608832 2022-07-27T10:37:20 Z MadokaMagicaFan Match (CEOI16_match) C++14
10 / 100
 2 ms 840 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)
        p[i][0] = -1;

    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]);
    }

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

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

    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+1);
    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

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

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 328 KB Output is correct
3 Correct 0 ms 324 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 0 ms 324 KB Output is correct
4 Runtime error 2 ms 840 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 0 ms 324 KB Output is correct
4 Runtime error 2 ms 840 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -