oj.uz

Submission #127253

# Submission time Handle Problem Language Result Execution time Memory
127253 2019-07-09T07:29:50 Z sealnot123 Match (CEOI16_match) C++14
10 / 100
 2 ms 376 KB 
#include<bits/stdc++.h>
#define x first
#define y second
#define all(x) (x).begin(),(x).end()
#define SZ(x) (int)(x).size()
#define push_back pb
#define emplace_back eb
using namespace std;
typedef long long LL;
typedef double DD;
typedef long double LD;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
const int N = 100007;
char str[N], ans[N];
int cnt[26], onstack[26];
stack<int> sta;
void PUSH(int a, int b){
	onstack[b]++;
	sta.push(a);
}
void POP(int b){
	onstack[b]--;
	sta.pop();
}
void del(){
	int a = sta.top(), b = str[a]-'a', c;
	POP(b);
	while(!sta.empty() && str[sta.top()]-'a' != b){
		c = sta.top();
		del();
		if(!sta.empty() && c == sta.top()) break;
	}
	if(sta.empty()){
		PUSH(a, b);
		return ;
	}
	if(str[sta.top()]-'a' != b){
		if(2*onstack[b]>=cnt[b]){ printf("-1"); exit(0);
		}else{ PUSH(a, b); return ; }
	}
	POP(b);
	ans[a] = ')';
	cnt[b] -= 2;
}
int main(){
	int i,j,k,l,a,b,c,d;
	scanf("%s",str+1);
	int n = strlen(str+1);
	for(i=1;i<=n;i++) cnt[str[i]-'a']++;
	for(i=0;i<26;i++){
		if(cnt[i]&1){
			printf("-1");
			return 0;
		}
	}
	for(i=1;i<=n;i++){
		a = str[i]-'a';
		ans[i] = '(';
		PUSH(i, a);
		if(2*onstack[a] > cnt[a]) del();
		/*printf("==%d %s\n",i,ans+1);*/
	}
	d = 0;
	for(i=1;i<=n;i++){
		d += (ans[i]=='(')?1:-1;
		if(d<0) assert(0);
	}
	printf("%s",ans+1);
	return 0;
}
/*
abbccddabbccdd
abbacabbac
accaccacca
aaaabbbb
aaabcaacba (()((())))
*/

Compilation message

match.cpp: In function 'int main()':
match.cpp:47:8: warning: unused variable 'j' [-Wunused-variable]
  int i,j,k,l,a,b,c,d;
        ^
match.cpp:47:10: warning: unused variable 'k' [-Wunused-variable]
  int i,j,k,l,a,b,c,d;
          ^
match.cpp:47:12: warning: unused variable 'l' [-Wunused-variable]
  int i,j,k,l,a,b,c,d;
            ^
match.cpp:47:16: warning: unused variable 'b' [-Wunused-variable]
  int i,j,k,l,a,b,c,d;
                ^
match.cpp:47:18: warning: unused variable 'c' [-Wunused-variable]
  int i,j,k,l,a,b,c,d;
                  ^
match.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",str+1);
  ~~~~~^~~~~~~~~~~~

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 252 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 252 KB Output is correct
4 Incorrect 2 ms 292 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 252 KB Output is correct
4 Incorrect 2 ms 292 KB Output isn't correct
5 Halted 0 ms 0 KB -