Submission #613888

#	Time	Username	Problem	Language	Result	Execution time	Memory
613888		MadokaMagicaFan	Match (CEOI16_match)	C++14	100 / 100	11 ms	11212 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+10;
const int K = 26;

int st[N][K];


#ifdef ONPC
void
solve()
{
    string s;
    int n, j, l;
    vector<int> t;
    cin >> s;
    n = sz(s);
    string ans(n, ')');
    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 k = 0; k < K; ++k) {
            st[i][k]=-1;
        }
    }

    st[0][t[0]]=0;
    for (int i = 1; i < n; ++i) {
        j = st[i-1][t[i]];
        if (j>0) {
            for (int k = 0; k < K; ++k) {
                st[i][k] = st[j-1][k];
            }
            st[i][t[j-1]] = j-1;
        }

        st[i][t[i]] = i;
    }

    queue<array<int,2>> qr;

    qr.push({0,n-1});

    bool p = 0;

    while (sz(qr)) {
        auto u = qr.front();
        qr.pop();
        if (u[0] >  u[1]) continue;
        if (u[0] == u[1]) {
            p = 1; break;
        }
        ans[u[0]] = '(';

        if (u[0] == u[1]-1) {
            if (t[u[0]] != t[u[1]]) {
                p = 1; break;
            }
            continue;
        }

        j = st[u[1]][t[u[0]]];

        if (j <= u[0]) {
            p = 1; break;
        }

        qr.push({u[0]+1, j-1});
        qr.push({j+1, u[1]});
    }

    if (p) {
        cout << -1 << endl;
        return;
    }

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

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