oj.uz

Submission #745457

# Submission time Handle Problem Language Result Execution time Memory
745457 2023-05-20T07:37:16 Z alexdumitru Match (CEOI16_match) C++14
10 / 100
 1 ms 340 KB 
#include <bits/stdc++.h>

using namespace std;

ifstream fin("match.in");
ofstream fout("match.out");

const int NMAX = 100005;

string s;
int n;
int a[NMAX];
int sir[NMAX];
int dp[26][NMAX];

void divide(int st, int dr)
{
    if(st > dr)
        return;
    int pos = dp[a[st]][dr];
    sir[st] = 1;
    sir[pos] = -1;
    divide(st + 1, pos - 1);
    divide(pos + 1, dr);
}

void solve()
{
    cin >> s;
    n = s.length();
    for(int i = 0; i < n; i++)
        a[i + 1] = s[i] - 'a';
    stack<int> st;
    for(int i = 1; i <= n; i++)
    {
        if(!st.empty() && st.top() == a[i])
            st.pop();
        else {
            st.push(a[i]);
        }
    }
    if(!st.empty())
    {
        cout << -1 << '\n';
        return;
    }
    for(int i = 1; i <= n; i++)
    {
        dp[a[i]][i] = i;
        if(i > 1)
        {
            for(int j = 0; j < 26; j++)
                if(j != a[i] && dp[j][i - 1])
                    dp[j][i] = dp[j][dp[j][i - 1]];
        }
    }
    divide(1, n);
    for(int i = 1; i <= n; i++)
    {
        if(sir[i] == 1)
            cout << '(';
        else cout << ')';
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -