Submission #197792

#	Time	Username	Problem	Language	Result	Execution time	Memory
197792		Windazz	Match (CEOI16_match)	C++14	100 / 100	97 ms	11636 KiB

match

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define x first
#define y second
#define ndl '\n'
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define up_b upper_bound
#define low_b lower_bound
#define sz(x) (int)x.size()
#define bit __builtin_popcount
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

using namespace std;
using namespace __gnu_pbds;

template<typename T> using indexed_set = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<int, ull> piu;
typedef vector<vector<int>> matrix;

const ll INF = 1e18 + 123;
const ld EPS = 1e-9;
const int inf = 1e9 + 123;
const int MOD = 1e9 + 7;
const int N = 1e5 + 13;
const int M = 1e6 + 123;
const double pi = acos(-1.0);
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};

string s;

char ans[N];

int dp[N][26], mn[N];

void solve(int l, int r){
    if (l > r) return;
    //cout <<l<< " " << r << endl;
    if (l%2 == r%2){
        cout << -1;
        exit(0);
    }
    if (s[l] == s[r]){
        ans[l] = '(';
        ans[r] = ')';
        solve(l+1, r-1);
    }
    else{
        if (dp[r][s[l]] <= l){
            cout << -1;
            exit(0);
        }
        solve(l, dp[r][s[l]]);
        solve(dp[r][s[l]]+1, r);
    }
}

int main(){
    #ifdef KAZAKH
        freopen("input.txt", "r", stdin);
    #endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> s;

    int n = sz(s);
    s = "$" + s;

    for (int i = 1; i <= n; i++){
        s[i] -= 'a';
        if (s[i] == s[i-1]){
            mn[i] = i-1;
        }
        else{
            mn[i] = dp[i-1][s[i]];
        }
        int j = i;
        while (j > 0){
            j = mn[j] - 1;
            if (j > 0 && !dp[i][s[j]]){
                dp[i][s[j]] = j;
            }
        }
       // cout <<i << " "<< dp[i][0] << " " << dp[i][1] << " " << dp[i][2] << endl;
    }

    solve(1, n);

    for (int i = 1; i <= n; i++){
        cout << ans[i];
    }

    return 0;
}

Compilation message (stderr)

match.cpp: In function 'void solve(int, int)':
match.cpp:62:23: warning: array subscript has type 'char' [-Wchar-subscripts]
         if (dp[r][s[l]] <= l){
                       ^
match.cpp:66:28: warning: array subscript has type 'char' [-Wchar-subscripts]
         solve(l, dp[r][s[l]]);
                            ^
match.cpp:67:25: warning: array subscript has type 'char' [-Wchar-subscripts]
         solve(dp[r][s[l]]+1, r);
                         ^
match.cpp: In function 'int main()':
match.cpp:88:33: warning: array subscript has type 'char' [-Wchar-subscripts]
             mn[i] = dp[i-1][s[i]];
                                 ^
match.cpp:93:37: warning: array subscript has type 'char' [-Wchar-subscripts]
             if (j > 0 && !dp[i][s[j]]){
                                     ^
match.cpp:94:27: warning: array subscript has type 'char' [-Wchar-subscripts]
                 dp[i][s[j]] = j;
                           ^

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