oj.uz

Submission #26541

# Submission time Handle Problem Language Result Execution time Memory
26541 2017-07-02T14:34:58 Z bill_kondo Match (CEOI16_match) C++11
37 / 100
 1173 ms 25848 KB 
#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 <= 2000) solve1();
	printf("%s\n",ans);
	return 0;
}

Compilation message

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.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 25848 KB Output is correct
2 Correct 3 ms 25848 KB Output is correct
3 Correct 0 ms 25848 KB Output is correct
4 Correct 326 ms 25848 KB Output is correct
5 Correct 493 ms 25848 KB Output is correct
6 Correct 36 ms 25848 KB Output is correct
7 Correct 1173 ms 25848 KB Output is correct

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 25848 KB Output is correct
2 Correct 3 ms 25848 KB Output is correct
3 Correct 0 ms 25848 KB Output is correct
4 Correct 326 ms 25848 KB Output is correct
5 Correct 493 ms 25848 KB Output is correct
6 Correct 36 ms 25848 KB Output is correct
7 Correct 1173 ms 25848 KB Output is correct
8 Incorrect 0 ms 25848 KB Output isn't correct
9 Halted 0 ms 0 KB -