oj.uz

Submission #390718

# Submission time Handle Problem Language Result Execution time Memory
390718 2021-04-16T18:25:01 Z Vladth11 Match (CEOI16_match) C++14
37 / 100
 2000 ms 37060 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define debug(x) cerr << #x << " " << x << "\n"
#define debug_with_space(x) cerr << #x << " " << x << " "

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <long double, pii> muchie;
typedef tree <ll, null_type, less_equal <ll>, rb_tree_tag, tree_order_statistics_node_update> OST;

const ll NMAX = 100001;
const ll INF = (1LL << 60);
const ll MOD = 1000000007;
const ll BLOCK = 225;
const ll base = 31;
const ll nr_of_bits = 21;

class Hashes {
    ll base, mod;
public:
    ll value = 0;
    Hashes(ll _base, ll _MOD) {
        base = _base;
        mod = _MOD;
    }
    ll lgput(ll n, ll p) {
        ll r = 1;
        while(p) {
            if(p % 2) {
                r *= n;
                r %= mod;
            }
            n *= n;
            n %= mod;
            p /= 2;
        }
        return r;
    }
    void insert(ll x) {
        value = value * base;
        value += x;
        value %= mod;
    }
    void erase(ll x) {
        value -= x;
        if(value < 0) {
            value += mod;
        }
        value = (value * lgput(base, mod - 2)) % mod;
    }
} H(31, MOD);

int inainte[NMAX];
int dupa[NMAX];
set <int> v[28];
string rez;
string s;

void solve(int l, int r) {
    int pz;
    if(l > r)
        return;
    stack <int> st;
    int last = 8;
    if(st.empty() && s[l] == s[l + 1] && rez[l + 1] != '(' && rez[l + 1] != ')')
        last = l + 1;
    for(ll i = l + 1; i < r; i++) {
        ll c = s[i] - 'a' + 1;
        if(st.size() && st.top() == c) {
            st.pop();
        } else {
            st.push(c);
        }
        if(st.empty() && s[l] == s[i + 1])
            last = i + 1;
    }
    rez[last] = ')';
    rez[l] = '(';
    solve(l + 1, last - 1);
    solve(last + 1, r);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> s;
    rez = s;
    stack <ll> st;
    for(ll i = 0; i < s.size(); i++) {
        ll c = s[i] - 'a' + 1;
        v[c].insert(i);
        inainte[i] = H.value;
        if(st.size() && st.top() == c) {
            H.erase(st.top());
            st.pop();
        } else {
            H.insert(c);
            st.push(c);
        }
        dupa[i] = H.value;
    }
    if(st.size()) {
        cout << -1;
        return 0;
    }
    solve(0, s.size() - 1);
    cout << rez;
    return 0;
}

Compilation message

match.cpp: In function 'void solve(int, int)':
match.cpp:63:9: warning: unused variable 'pz' [-Wunused-variable]
   63 |     int pz;
      |         ^~
match.cpp: In function 'int main()':
match.cpp:93:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     for(ll i = 0; i < s.size(); i++) {
      |                   ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 316 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 4 ms 972 KB Output is correct
7 Correct 3 ms 588 KB Output is correct

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 4 ms 972 KB Output is correct
7 Correct 3 ms 588 KB Output is correct
8 Correct 8 ms 844 KB Output is correct
9 Correct 47 ms 2244 KB Output is correct
10 Correct 28 ms 1996 KB Output is correct
11 Correct 46 ms 3356 KB Output is correct
12 Correct 1907 ms 30412 KB Output is correct
13 Execution timed out 2071 ms 37060 KB Time limit exceeded
14 Halted 0 ms 0 KB -