oj.uz

Submission #35576

# Submission time Handle Problem Language Result Execution time Memory
35576 2017-11-25T16:40:09 Z imaxblue Match (CEOI16_match) C++14
100 / 100
 46 ms 7968 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, r[100005], len[100005];
string s;
char ans[100005];
bool U[100005];
set<int> u, pos[30];
int solve(int P){
    if (U[P]) return len[P];
    U[P]=1;
    int k=P-1;
    //cout << "%" << P << endl;
    while(k>=0 && s[k]!=s[P]){
        k=solve(k)-1;
        //cout << P << endl;
        //if (P<=941) cout << P << ' ' << k << endl;
    }
    len[P]=max(-1, k);
    //cout << "*" << P << ' ' << len[P] << ' ';
    return len[P];
}
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);
    }
    int p=R;
    while(p>L && s[p]!=s[L]){
        p=solve(p)-1;
        //cout << p << endl;
    }
    //cout << "^";
    if (p>L){
        return (dfs(L, p) && dfs(p+1, R));
    }
    return 0;
}
int main(){
    cin >> s; n=s.size();
    fox(l, s.size()){
        pos[s[l]-'a'].insert(l);
    }

    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:67: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 2996 KB Output is correct
2 Correct 0 ms 2996 KB Output is correct
3 Correct 0 ms 2996 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2996 KB Output is correct
2 Correct 0 ms 2996 KB Output is correct
3 Correct 0 ms 2996 KB Output is correct
4 Correct 0 ms 2996 KB Output is correct
5 Correct 0 ms 2996 KB Output is correct
6 Correct 0 ms 3128 KB Output is correct
7 Correct 0 ms 3128 KB Output is correct

Subtask #3
63.0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2996 KB Output is correct
2 Correct 0 ms 2996 KB Output is correct
3 Correct 0 ms 2996 KB Output is correct
4 Correct 0 ms 2996 KB Output is correct
5 Correct 0 ms 2996 KB Output is correct
6 Correct 0 ms 3128 KB Output is correct
7 Correct 0 ms 3128 KB Output is correct
8 Correct 0 ms 3260 KB Output is correct
9 Correct 0 ms 3392 KB Output is correct
10 Correct 0 ms 3392 KB Output is correct
11 Correct 3 ms 3392 KB Output is correct
12 Correct 19 ms 6000 KB Output is correct
13 Correct 19 ms 6340 KB Output is correct
14 Correct 26 ms 6532 KB Output is correct
15 Correct 23 ms 6876 KB Output is correct
16 Correct 26 ms 6876 KB Output is correct
17 Correct 23 ms 7184 KB Output is correct
18 Correct 36 ms 7404 KB Output is correct
19 Correct 36 ms 7660 KB Output is correct
20 Correct 23 ms 6060 KB Output is correct
21 Correct 46 ms 7968 KB Output is correct