제출 #157528

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
157528		shayan_p	괄호 문자열 (CEOI16_match)	C++14	0 / 100	2073 ms	2680 KiB

match

// 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;
	    TLE(id>=0 && id<=sz(v[i]) && i<v[i][id] && v[i][id]<st.top() );
	    st.push( v[i][id] );
	    if(nxt[i]!=n+1)
		swap(v[i], v[ nxt[i] ]);
	    cout<<'(';
	}
    }
    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: 0 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 63