Submission #74018

#	Time	Username	Problem	Language	Result	Execution time	Memory
74018		ikura355	Match (CEOI16_match)	C++17	100 / 100	969 ms	56592 KiB

match

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e5 + 5;
const ll mod = 1e9 + 7;
int n;
char s[maxn];
int sz, stk[maxn];
int rec[30][maxn];
unordered_map<int,int> pos[30];
char res[maxn];
ll add(ll x, ll y) {
	return ((x+y)%mod + mod)%mod;
}
ll mul(ll x, ll y) {
	return ((x*y)%mod + mod)%mod;
}
ll inv(ll x, ll y) {
	return 1<x ? y - inv(y%x,x)*y/x : 1;
}
void solve(int l, int r) {
	if(l>r) return ;
//	printf("solve %d %d\n",l,r);
	int x = rec[s[l]-'a'][r];
    res[l] = '('; res[x] = ')';
	if(l+1!=r) {
        solve(l+1,x-1);
        solve(x+1,r);
	}
}
int main() {
	scanf(" %s",s+1);
	n = strlen(s+1);
	ll hsh = 0;
	for(int i=1;i<=n;i++) {
		if(sz && stk[sz]==s[i]) {
			sz--;
			hsh = add(hsh, -s[i]);
			hsh = mul(hsh, inv(101,mod));
		}
		else {
            stk[++sz] = s[i];
            hsh = add(mul(hsh,101), s[i]);
		}
		pos[s[i]-'a'][hsh] = i;
		for(int x=0;x<26;x++) rec[x][i] = pos[x][hsh];
//		printf("hsh = %d\n",(int)hsh);
	}
	if(hsh!=0) return !printf("-1");
	solve(1,n);
	printf("%s",res+1);
}

Compilation message (stderr)

match.cpp: In function 'int main()':
match.cpp:32:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf(" %s",s+1);
  ~~~~~^~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 63 / 63