oj.uz

Submission #35559

# Submission time Handle Problem Language Result Execution time Memory
35559 2017-11-24T23:22:08 Z imaxblue Match (CEOI16_match) C++14
10 / 100
 0 ms 2900 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define pii pair<int, int>
#define p3i pair<pii, int>
#define pll pair<ll, ll>
#define p3l pair<pll, ll>
#define lseg L, (L+R)/2, N*2+1
#define rseg (L+R)/2+1, R, N*2+2
#define ub upper_bound
#define lb lower_bound
#define pq priority_queue
#define MN 1000000007
#define fox(k, x) for (int k=0; k<x; ++k)
#define fox1(k, x) for (int k=1; k<=x; ++k)
#define foxr(k, x) for (int k=x-1; k>=0; --k)
#define fox1r(k, x) for (int k=x; k>0; --k)
#define ms multiset
#define flood(x) memset(x, 0x3f3f3f3f, sizeof x)
#define drain(x) memset(x, 0, sizeof x)
#define rng() (rand() >> 3)*rand()

int n, rit=-1, p, t, r[100005], len[100005];
string s, s2="#";
char ans[100005];
set<int> u, pos[30];
set<int>::iterator i;
bool pal(int L, int R){
    if ((L+R)%2==0) return 0;
    //cout << "^" << r[L+R+1] << endl;
    if (r[L+R+1]/2>=(R-L+1)/2) return 1;
    return 0;
}
bool dfs(int L, int R){
    //cout << L << ' ' << R << endl;
    if (L>R) return 1;
    if (s[L]==s[R]){
        ans[L]='(';
        ans[R]=')';
        return dfs(L+1, R-1);
    }
    i=--pos[s[L]-'a'].ub(R);
    while(i!=pos[s[L]-'a'].lb(L)){
        //cout << *i << endl;
        if (pal(*i+1, R) && (dfs(L, *i) && dfs(*i+1, R))){
            return 1;
        }
        --i;
    }
    return 0;
}
int main(){
    cin >> s;
    fox(l, s.size()){
        pos[s[l]-'a'].insert(l);
        s2+=(s[l]); s2+='#';
    }
    n=s2.size();
    fox(l, n){
        if (l>rit){
            rit=l;
            r[l]=0;
            p=l;
        } else {
            r[l]=r[2*p-l];
        }
        while(l-r[l]>0 && l+r[l]<n-1 && s2[l-r[l]-1]==s2[l+r[l]+1]) r[l]++;
        if (l+r[l]>rit){
            rit=l;
            p=l;
        }
    }
    //cout << s << endl;
    /*fox(l, n) u.insert(l);
    foxr(l, n){
        if (s2[l]!='#') continue;
        p=(l+1)/2;
        //cout << p << ' ' << r[l] << ' ' << (l+r[l])/2 << endl;
        while(u.lb(p)!=u.end() && *u.lb(p)<(l+r[l])/2){
            //cout << "*";
            t=*u.lb(p);
            u.erase(u.lb(p));
            len[t]=2*p-1-t;
        }
    }*/
    n/=2;
    if (dfs(0, n-1)==0) cout << -1;
    else {
        fox(l, n) cout << ans[l];
    }
    //fox(l, n) cout << len[l] << ' '; cout << endl;
    return 0;
}

Compilation message

match.cpp: In function 'int main()':
match.cpp:18:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
                                  ^
match.cpp:58:5: note: in expansion of macro 'fox'
     fox(l, s.size()){
     ^

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 27.0

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

Subtask #3
0 / 63.0

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