oj.uz

Submission #156169

# Submission time Handle Problem Language Result Execution time Memory
156169 2019-10-04T08:50:57 Z shayan_p Match (CEOI16_match) C++14
10 / 100
 2 ms 376 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, 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<sz(s);i++){
	int ch= s[i]-'a';
	if(lst[ch]==-1){
	    a[i]= 2*ch;
	}
	else{
	    bool any=0;
	    for(int j=0;j<Max;j++){
		any|= j!=2*ch && j!=2*ch+1 && (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][ a[i] ]^=1;
	
	lst[ch]=i;
    }
    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);
    }
    st.push(n);
    for(int i=0;i<n;i++){
	assert(sz(st));
	if(st.top()==i){
	    st.pop();
	    ans+=')';
	}
	else{	    
	    st.push( seg[ a[i] ].fnd(i+1,st.top()) );
	    assert(st.top()!=-1);
	    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.0 / 10.0

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

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Incorrect 2 ms 376 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Incorrect 2 ms 376 KB Output isn't correct
5 Halted 0 ms 0 KB -