oj.uz

Submission #157530

# Submission time Handle Problem Language Result Execution time Memory
157530 2019-10-12T08:18:43 Z shayan_p Match (CEOI16_match) C++14
100 / 100
 32 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];

void TLE(bool is){
    if(is==0){
	while(true){
	}
    }
}

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 4 ms 2680 KB Output is correct
2 Correct 4 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 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 4 ms 2808 KB Output is correct
5 Correct 4 ms 2808 KB Output is correct
6 Correct 4 ms 2936 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 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 4 ms 2808 KB Output is correct
5 Correct 4 ms 2808 KB Output is correct
6 Correct 4 ms 2936 KB Output is correct
7 Correct 4 ms 2936 KB Output is correct
8 Correct 6 ms 3576 KB Output is correct
9 Correct 6 ms 3576 KB Output is correct
10 Correct 6 ms 3576 KB Output is correct
11 Correct 6 ms 3576 KB Output is correct
12 Correct 19 ms 10492 KB Output is correct
13 Correct 20 ms 11128 KB Output is correct
14 Correct 21 ms 11768 KB Output is correct
15 Correct 21 ms 12408 KB Output is correct
16 Correct 21 ms 12408 KB Output is correct
17 Correct 23 ms 13288 KB Output is correct
18 Correct 23 ms 13432 KB Output is correct
19 Correct 32 ms 14840 KB Output is correct
20 Correct 20 ms 10492 KB Output is correct
21 Correct 30 ms 15352 KB Output is correct