oj.uz

Submission #197792

# Submission time Handle Problem Language Result Execution time Memory
197792 2020-01-23T08:11:09 Z Windazz Match (CEOI16_match) C++14
100 / 100
 97 ms 11636 KB 
#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

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

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 380 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 3 ms 632 KB Output is correct

Subtask #3
63.0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 380 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 3 ms 632 KB Output is correct
8 Correct 3 ms 1016 KB Output is correct
9 Correct 3 ms 1144 KB Output is correct
10 Correct 3 ms 1144 KB Output is correct
11 Correct 3 ms 1276 KB Output is correct
12 Correct 12 ms 7004 KB Output is correct
13 Correct 12 ms 7288 KB Output is correct
14 Correct 14 ms 8308 KB Output is correct
15 Correct 97 ms 9296 KB Output is correct
16 Correct 97 ms 9340 KB Output is correct
17 Correct 18 ms 9972 KB Output is correct
18 Correct 75 ms 10380 KB Output is correct
19 Correct 19 ms 10996 KB Output is correct
20 Correct 12 ms 7160 KB Output is correct
21 Correct 21 ms 11636 KB Output is correct