oj.uz

Submission #506987

# Submission time Handle Problem Language Result Execution time Memory
506987 2022-01-12T08:15:32 Z CyberSleeper Match (CEOI16_match) C++14
100 / 100
 13 ms 14796 KB 
#include <bits/stdc++.h>
#define fastio      ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define debug(x)    cout << "Line " << __LINE__ << ", " << #x << " is " << x << endl
#define all(x)      x.begin(), x.end()
#define fi          first
#define se          second
#define mp          make_pair
#define pb          push_back
#define ll          long long
#define ull         unsigned long long
#define pll         pair<ll, ll>
#define ld          long double
#define nl          '\n'
#define tb          '\t'
#define sp          ' '
using namespace std;

const ll MX=100005, MOD=1e9+7, BLOCK=327, INF=2e9+7;
const ll INFF=4e18+7;

const ld ERR=1e-7, pi=3.14159265358979323846;

string S, ans;
int N, bef[MX][28];

bool cek(){
    vector<int> vec;
    for(int i=0; i<N; i++){
        if(vec.size() && S[i]==S[vec.back()]){
            vec.pop_back();
        }else{
            vec.pb(i);
        }
    }
    return vec.empty();
}
void rec(int le, int ri){
    if(ri<le)
        return;
    int mi=bef[ri][S[le]-'a'];
    ans.pb('(');
    rec(le+1, mi-1);
    ans.pb(')');
    rec(mi+1, ri);
}

int main(){
    fastio;
    cin >> S;
    N=S.size();
    if(!cek()){
        cout << "-1\n";
        return 0;
    }
    memset(bef, -1, sizeof(bef));
    bef[0][S[0]-'a']=0;
    for(int i=1; i<N; i++){
        for(int j=0, now; j<26; j++){
            if((S[i]-'a')==j)
                bef[i][j]=i;
            else{
                now=bef[i-1][S[i]-'a'];
                if(now>0)
                    bef[i][j]=bef[now-1][j];
            }
        }
    }
    rec(0, N-1);
    cout << ans << nl;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11204 KB Output is correct
2 Correct 5 ms 11200 KB Output is correct
3 Correct 0 ms 204 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11204 KB Output is correct
2 Correct 5 ms 11200 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 4 ms 11208 KB Output is correct
5 Correct 5 ms 11212 KB Output is correct
6 Correct 4 ms 11336 KB Output is correct
7 Correct 5 ms 11212 KB Output is correct

Subtask #3
63.0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11204 KB Output is correct
2 Correct 5 ms 11200 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 4 ms 11208 KB Output is correct
5 Correct 5 ms 11212 KB Output is correct
6 Correct 4 ms 11336 KB Output is correct
7 Correct 5 ms 11212 KB Output is correct
8 Correct 6 ms 11212 KB Output is correct
9 Correct 5 ms 11340 KB Output is correct
10 Correct 4 ms 11340 KB Output is correct
11 Correct 5 ms 11592 KB Output is correct
12 Correct 11 ms 12944 KB Output is correct
13 Correct 10 ms 13260 KB Output is correct
14 Correct 11 ms 13804 KB Output is correct
15 Correct 11 ms 14660 KB Output is correct
16 Correct 12 ms 14744 KB Output is correct
17 Correct 12 ms 14796 KB Output is correct
18 Correct 12 ms 12996 KB Output is correct
19 Correct 12 ms 13644 KB Output is correct
20 Correct 9 ms 13316 KB Output is correct
21 Correct 13 ms 14144 KB Output is correct