oj.uz

답안 #157531

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
157531 2019-10-12T08:19:40 Z shayan_p 괄호 문자열 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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