oj.uz

Submission #157531

# Submission time Handle Problem Language Result Execution time Memory
157531 2019-10-12T08:19:40 Z shayan_p Match (CEOI16_match) C++14
100 / 100
 29 ms 15352 KB 
// Remember...
 
#include<bits/stdc++.h>
 
#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
 
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
const int maxn=1e5+10;
 
int dp[maxn][26], f[maxn], nxt[maxn];
vector<int> v[maxn];
bool mark[maxn];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();

    string s; cin>>s;
    int n= sz(s);

    memset(dp[0],-1,sizeof dp[0]);
    f[0]=-1;
    
    for(int i=0;i<sz(s);i++){
	int ch=s[i]-'a';
	f[i+1]= max( dp[i][ch]-1, -1 );
	dp[i+1][ch]= i+1;
	
	for(int j=0;j<26;j++){
	    if(ch==j) continue;
	    dp[i+1][j]= f[i+1]==-1 ? -1 : dp[f[i+1]][j];
	}
    }
    
    int tmp=n;
    while(tmp>0){
	tmp=f[tmp];
    }
    if(tmp!=0) return cout<<-1<<endl,0;

    for(int i=n;i>0;i--){
	if(mark[i]) continue;
	nxt[i]= n+1;
	int tmp=i;
	while(tmp>0){
	    mark[tmp]=1;
	    v[i].PB(tmp);
	    nxt[ f[tmp]+1 ]= tmp;
	    tmp= f[tmp]+1;
	}
	reverse( v[i].begin(), v[i].end() );
	swap( v[ v[i][0] ], v[i] );	
    }

    stack<int> st;
    st.push(n+1);
    
    for(int i=1;i<=n;i++){
	if(st.top()==i){
	    cout<<')';
	    st.pop();
	}
	else{
	    int id= lower_bound(v[i].begin(), v[i].end(), st.top() )- v[i].begin() -1;
	    st.push( v[i][id] );
	    cout<<'(';
	}
	if(nxt[i]!=n+1)
	    swap(v[i], v[ nxt[i] ]);
	
    }
    return cout<<endl,0;
}
// Deathly mistakes:
//  * Read the problem carefully.
//  * Check maxn.
//  * Overflows.
 
 
// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2680 KB Output is correct
2 Correct 5 ms 2680 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2680 KB Output is correct
2 Correct 5 ms 2680 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 5 ms 2808 KB Output is correct
5 Correct 4 ms 2808 KB Output is correct
6 Correct 4 ms 2808 KB Output is correct
7 Correct 4 ms 2936 KB Output is correct

Subtask #3
63.0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2680 KB Output is correct
2 Correct 5 ms 2680 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 5 ms 2808 KB Output is correct
5 Correct 4 ms 2808 KB Output is correct
6 Correct 4 ms 2808 KB Output is correct
7 Correct 4 ms 2936 KB Output is correct
8 Correct 6 ms 3576 KB Output is correct
9 Correct 7 ms 3576 KB Output is correct
10 Correct 6 ms 3580 KB Output is correct
11 Correct 6 ms 3576 KB Output is correct
12 Correct 21 ms 10488 KB Output is correct
13 Correct 20 ms 11000 KB Output is correct
14 Correct 21 ms 11640 KB Output is correct
15 Correct 21 ms 12408 KB Output is correct
16 Correct 21 ms 12280 KB Output is correct
17 Correct 24 ms 13176 KB Output is correct
18 Correct 22 ms 13432 KB Output is correct
19 Correct 28 ms 14840 KB Output is correct
20 Correct 19 ms 10488 KB Output is correct
21 Correct 29 ms 15352 KB Output is correct