oj.uz

Submission #116649

# Submission time Handle Problem Language Result Execution time Memory
116649 2019-06-13T10:06:15 Z JohnTitor Match (CEOI16_match) C++11
100 / 100
 17 ms 11164 KB 
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k) for(int i=(j); i<=(k); i++)
#define FFOR(i, j, k) for(int i=(j); i<(k); i++)
#define DFOR(i, j, k) for(int i=(j); i>=(k); i--)
#define bug(x) cerr<<#x<<" = "<<(x)<<'\n'
#define pb push_back
#define mp make_pair
#define bit(s, i) (((s)>>(i))&1LL)
#define mask(i) ((1LL<<(i)))
#define builtin_popcount __builtin_popcountll
#define __builtin_popcount __builtin_popcountll
using ll=long long; using ld=long double;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); const ld pi=acos(0)*2;
template <typename T> inline void read(T &x){char c; bool nega=0; while((!isdigit(c=getchar()))&&(c!='-')); if(c=='-'){nega=1; c=getchar();} x=c-48; while(isdigit(c=getchar())) x=x*10+c-48; if(nega) x=-x;}
template <typename T> inline void writep(T x){if(x>9) writep(x/10); putchar(x%10+48);}
template <typename T> inline void write(T x){if(x<0){ putchar('-'); x=-x;} writep(x);}
template <typename T> inline void writeln(T x){write(x); putchar('\n');}
#define taskname "Match"
string s;
int cnt[256];
string t;
vector <char> v;
int f[100000][26];
void kill(){
    puts("-1");
    exit(0);
}
void make(int l, int r){
    if(l>r) return;
    if((r-l+1)%2) kill();
//    cerr<<l<<' '<<r<<'\n';
    t[l]='(';
    t[r]=')';
    if(s[l]==s[r]){
        make(l+1, r-1);
    }
    else{
        if(f[r][s[l]]<=l) kill();
        make(l, f[r][s[l]]);
        make(f[r][s[l]]+1, r);
    }
}
int main(){
    #ifdef Aria
        if(fopen(taskname".in", "r"))
            freopen(taskname".in", "r", stdin);
    #endif // Aria
    cin>>s;
    for(char &c: s) c-='a';
    for(char c: s) cnt[c]++;
    FFOR(c, 0, 26) if(cnt[c]%2){
        puts("-1");
        return 0;
    }
    FFOR(i, 0, 26) f[0][i]=-1;
    FFOR(i, 0, 26) f[1][i]=-1;
    FFOR(i, 2, s.size()){
        if(s[i]==s[i-1]){
            FFOR(j, 0, 26) f[i][j]=f[i-2][j];
            f[i][s[i-2]]=i-2;
        }
        else if(f[i-1][s[i]]>0){
            ///match f[i-1][s[i]] to i
            FFOR(j, 0, 26) f[i][j]=f[f[i-1][s[i]]-1][j];
            f[i][s[f[i-1][s[i]]-1]]=f[i-1][s[i]]-1;
        }
        else FFOR(j, 0, 26) f[i][j]=-1;
//        FFOR(j, 0, 26) cerr<<f[i][j]<<" \n"[j+1==26];
    }
    t=s;
    make(0, s.size()-1);
    cout<<t<<'\n';
}

Compilation message

match.cpp: In function 'void make(int, int)':
match.cpp:39:21: warning: array subscript has type 'char' [-Wchar-subscripts]
         if(f[r][s[l]]<=l) kill();
                     ^
match.cpp:40:26: warning: array subscript has type 'char' [-Wchar-subscripts]
         make(l, f[r][s[l]]);
                          ^
match.cpp:41:23: warning: array subscript has type 'char' [-Wchar-subscripts]
         make(f[r][s[l]]+1, r);
                       ^
match.cpp: In function 'int main()':
match.cpp:51:25: warning: array subscript has type 'char' [-Wchar-subscripts]
     for(char c: s) cnt[c]++;
                         ^
match.cpp:4:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FFOR(i, j, k) for(int i=(j); i<(k); i++)
                                       ^
match.cpp:58:5: note: in expansion of macro 'FFOR'
     FFOR(i, 2, s.size()){
     ^~~~
match.cpp:61:24: warning: array subscript has type 'char' [-Wchar-subscripts]
             f[i][s[i-2]]=i-2;
                        ^
match.cpp:63:28: warning: array subscript has type 'char' [-Wchar-subscripts]
         else if(f[i-1][s[i]]>0){
                            ^
match.cpp:65:49: warning: array subscript has type 'char' [-Wchar-subscripts]
             FFOR(j, 0, 26) f[i][j]=f[f[i-1][s[i]]-1][j];
                                                 ^
match.cpp:66:31: warning: array subscript has type 'char' [-Wchar-subscripts]
             f[i][s[f[i-1][s[i]]-1]]=f[i-1][s[i]]-1;
                               ^
match.cpp:66:35: warning: array subscript has type 'char' [-Wchar-subscripts]
             f[i][s[f[i-1][s[i]]-1]]=f[i-1][s[i]]-1;
                                   ^
match.cpp:66:48: warning: array subscript has type 'char' [-Wchar-subscripts]
             f[i][s[f[i-1][s[i]]-1]]=f[i-1][s[i]]-1;
                                                ^

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 2 ms 612 KB Output is correct

Subtask #3
63.0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 2 ms 612 KB Output is correct
8 Correct 3 ms 1024 KB Output is correct
9 Correct 3 ms 1024 KB Output is correct
10 Correct 3 ms 1024 KB Output is correct
11 Correct 4 ms 1024 KB Output is correct
12 Correct 10 ms 6656 KB Output is correct
13 Correct 11 ms 7296 KB Output is correct
14 Correct 12 ms 7936 KB Output is correct
15 Correct 15 ms 8832 KB Output is correct
16 Correct 13 ms 8832 KB Output is correct
17 Correct 14 ms 9344 KB Output is correct
18 Correct 15 ms 9856 KB Output is correct
19 Correct 15 ms 10468 KB Output is correct
20 Correct 10 ms 6784 KB Output is correct
21 Correct 17 ms 11164 KB Output is correct