Submission #26540

#	Time	Username	Problem	Language	Result	Execution time	Memory
26540		bill_kondo	Match (CEOI16_match)	C++11	10 / 100	3 ms	25848 KiB

match

#include "bits/stdc++.h"
using namespace std;

#define FOR(i,a,b) for(int i = a; i <= b; ++i)
#define REP(i,a,b) for(int i = a; i >= b; --i)
#define pb push_back

const int maxn = 2e5 + 10;
const int maxc = 30;

int n;
char s[maxn];

bool can(int l, int r){
	vector<char>stk;
	FOR(i,l,r){
		if(stk.empty()) stk.pb(s[i]);
		else{
			if(stk.back() == s[i]) stk.pop_back();
			else stk.pb(s[i]);
		}
	}
	return stk.empty();
}

int pre[maxc][maxn];
char ans[maxn];

void rec(int l, int r){
	if(l > r) return;
	int mid = pre[s[l] - 'a'][r];
	ans[l] = '(';
	ans[mid] = ')';
	rec(l + 1, mid - 1);
	rec(mid + 1, r);
}

void solve1(){
	memset(pre,-1,sizeof(pre));
	REP(i,n-1,0){
		pre[s[i]-'a'][i] = i;
		REP(j,i-1,0)
			if(pre[s[j]-'a'][i] == -1 && can(j+1,i))
				pre[s[j]-'a'][i] = j;
	}
	rec(0,n-1);
}

int main(){
	scanf("%s",s);
	n = strlen(s);
	if(!can(0,n-1)){
		printf("-1\n");
		return 0;
	}
	FOR(i,0,n) ans[i] = ' ';
	if(n <= 18) solve1();
	printf("%s\n",ans);
	return 0;
}

Compilation message (stderr)

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

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