제출 #156182

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
156182		shayan_p	괄호 문자열 (CEOI16_match)	C++14	10 / 100	2 ms	376 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, Max=60;
 
int a[maxn], lst[Max];
bool cnt[maxn][Max];
string ans;
stack<int> st;
 
struct Seg{
    bool is[4*maxn];
    void add(int pos,int l=0,int r=maxn,int id=1){
	is[id]=1;
	if(r-l==1) return;
	int mid=(l+r)>>1;
	if(pos<mid) add(pos,l,mid,2*id);
	else        add(pos,mid,r,2*id+1);
    }
    int fnd(int f,int s,int l=0,int r=maxn,int id=1){
	if(f>=s || l>=r || s<=l || r<=f) return -1;
	int mid=(l+r)>>1;
	if(f<=l && r<=s){
	    if(is[id]==0) return -1;
	    if(r-l==1) return l;
	    if(is[2*id+1]) return fnd(f,s,mid,r,2*id+1);
	    else           return fnd(f,s,l,mid,2*id);
	}
	int ans=fnd(f,s,mid,r,2*id+1);
	if(ans==-1) ans=fnd(f,s,l,mid,2*id);
	return ans;
    }
};
Seg seg[Max];
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();
 
    string s; cin>>s;
    int n=sz(s);
    memset(lst,-1,sizeof lst);
    
    for(int i=0;i<n;i++){
	int ch= s[i]-'a';
	if(lst[ch]==-1){
	    a[i]= 2*ch;
	}
	else{
	    bool any=0;
	    for(int j=0;j<26;j++){
		any|= j!=ch && (cnt[i][j]^cnt[ lst[ch] ][j]);
	    }
	    a[i]= a[ lst[ch] ] ^ any;	    
	}
	
	for(int j=0;j<Max;j++){
	    cnt[i+1][j]= cnt[i][j];
	}
	cnt[i+1][ch]^=1;
	
	lst[ch]=i;
    }
    for(int i=0;i<n;i++){
	for(int j=0;j<Max;j++)
	    cnt[i+1][j]= cnt[i][j];
	cnt[i+1][a[i]]^=1;
    }
    for(int i=0;i<Max;i++){
	if(cnt[n][i]) return cout<<-1<<endl,0;
    }
    for(int i=0;i<n;i++){
	seg[ a[i] ].add(i);
    }

    memset(lst,-1,sizeof lst);
    for(int i=0;i<n;i++){
	if(lst[a[i]]!=-1){
	    for(int j=0;j<Max;j++){
		if(j!=a[i] && (cnt[i][j]^cnt[ lst[a[i]] ][j])) assert(0);
	    }
	}
	lst[ a[i] ]=i;
    }
    
    st.push(n);
    for(int i=0;i<n;i++){
	assert(sz(st));
	if(st.top()==i){
	    st.pop();
	    ans+=')';
	}
	else{	    
	    int pos= seg[ a[i] ].fnd(i+1,st.top());
	    assert( i<pos && pos<st.top() && s[i] == s[pos] );
	    st.push(pos);	  
	    ans+='(';
	}
    }
    return cout<<ans<<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 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 63