oj.uz

Submission #129018

# Submission time Handle Problem Language Result Execution time Memory
129018 2019-07-11T12:36:12 Z davitmarg Match (CEOI16_match) C++17
10 / 100
 2000 ms 504 KB 
/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <stack>
#include <cassert>
#include <iterator>
#include <bitset>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(),v.end()
using namespace std;

LL h[100005],pr=173,a=1;
int p[100005][30],lst[30];
int n;
string s,ans;
vector<int> st;
map<LL,vector<int>> used;

void dfs(int l,int r)
{
	if(l>r)
		return;
	if(s[l]==s[r])
	{
        ans[l]='(';
        ans[r]=')';
		//cout<<"! "<<ans<<endl;
        dfs(l+1,r-1);
		return;
	}
    int m=p[r][s[l]-'a'];
    dfs(l,m);
    dfs(m+1,r);
}

int main()
{
    cin>>s;
    n=s.length();
    s="#"+s;
    ans=s;
    for(int i=1;i<=n;i++)
		if(!st.empty() && s[st.back()]==s[i])
		{
            h[i]=h[i-1]-(s[st.back()]-'a'+1ll)*a;
            a/=pr;
            st.pop_back();
		}
		else
		{
			st.PB(i);
			a*=pr;
            h[i]=h[i-1]+(s[i]-'a'+1ll)*a;
		}

    if(!st.empty())
	{
		cout<<-1<<endl;
        return 0;
	}
    for(int i=0;i<=n;i++)
		used[h[i]].PB(i);

    for(auto it=used.begin();it!=used.end();++it)
	{
        for(int j=0;j<26;j++)
			lst[j]=0;
        vector<int> x=it->second;
        for(int i=0;i<x.size();i++)
		{
			for(int j=0;j<26;j++)
				if(lst[j]!=-1)
					p[x[i]][j]=lst[j];
			//cout<<"!! "<<x[i]<<" "<<s[x[i]]<<endl;
            lst[s[x[i]]-'a']=x[i];
		}
	}

	dfs(1,n);
    for(int i=1;i<=n;i++)
		printf("%c",ans[i]);
	cout<<endl;
	return 0;
}


/*



bcabccddeffebgabccddeffebggagacddeffeb
cabccddeffebgabccddeffebggagacddeffe


*/

Compilation message

match.cpp: In function 'int main()':
match.cpp:82:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<x.size();i++)
                     ~^~~~~~~~~

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 364 KB Output is correct
3 Correct 2 ms 256 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 364 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Execution timed out 2019 ms 504 KB Time limit exceeded
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 364 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Execution timed out 2019 ms 504 KB Time limit exceeded
5 Halted 0 ms 0 KB -