oj.uz

Submission #613888

# Submission time Handle Problem Language Result Execution time Memory
613888 2022-07-30T12:27:34 Z MadokaMagicaFan Match (CEOI16_match) C++14
100 / 100
 11 ms 11212 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+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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct

Subtask #3
63.0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 980 KB Output is correct
9 Correct 1 ms 980 KB Output is correct
10 Correct 1 ms 980 KB Output is correct
11 Correct 1 ms 980 KB Output is correct
12 Correct 7 ms 6868 KB Output is correct
13 Correct 6 ms 7508 KB Output is correct
14 Correct 9 ms 7972 KB Output is correct
15 Correct 9 ms 9044 KB Output is correct
16 Correct 9 ms 9044 KB Output is correct
17 Correct 10 ms 9664 KB Output is correct
18 Correct 9 ms 10152 KB Output is correct
19 Correct 9 ms 10708 KB Output is correct
20 Correct 5 ms 6900 KB Output is correct
21 Correct 11 ms 11212 KB Output is correct