oj.uz

Submission #609733

# Submission time Handle Problem Language Result Execution time Memory
609733 2022-07-27T20:01:25 Z KrisjanisP Match (CEOI16_match) C++17
100 / 100
 15 ms 25264 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

string str, res;
const ll N = 1e5;
bool prevPos_visited[N][27];
ll prevPos_result[N][27];
bool bad = false;
ll prevPos(ll i, ll c)
{
    if(i<=0)
    {
        bad = true;
        return -1;
    }
    if((str[i]-'a')==c) return i;
    if(prevPos_visited[i][c])
        return prevPos_result[i][c];
    prevPos_visited[i][c] = 1;
    prevPos_result[i][c] = prevPos(prevPos(i-1,str[i]-'a')-1,c);
    return prevPos_result[i][c];
}

void construct(ll i, ll j)
{
    ll k;
    if((j-i)%2==0) bad=true;
    else k = prevPos(j,str[i]-'a');
    if(bad) return;
    res[i] = '(', res[k]=')';
    if(k-i>1)
        construct(i+1,k-1);
    if(k!=j)
        construct(k+1,j);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin>>str;
    ll n = str.size();
    res = str;
    construct(0,n-1);
    if(!bad)
        cout<<res<<"\n";
    else
        cout<<"-1\n";
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 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 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 468 KB Output is correct
5 Correct 0 ms 468 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 724 KB Output is correct

Subtask #3
63.0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 468 KB Output is correct
5 Correct 0 ms 468 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 1876 KB Output is correct
9 Correct 1 ms 2004 KB Output is correct
10 Correct 1 ms 1996 KB Output is correct
11 Correct 2 ms 2004 KB Output is correct
12 Correct 7 ms 14168 KB Output is correct
13 Correct 7 ms 14420 KB Output is correct
14 Correct 10 ms 17876 KB Output is correct
15 Correct 4 ms 5716 KB Output is correct
16 Correct 3 ms 5716 KB Output is correct
17 Correct 10 ms 21844 KB Output is correct
18 Correct 9 ms 16884 KB Output is correct
19 Correct 12 ms 23892 KB Output is correct
20 Correct 8 ms 15316 KB Output is correct
21 Correct 15 ms 25264 KB Output is correct