Submission #30818

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
30818	2017-07-27T05:02:18 Z	zscoder	Match (CEOI16_match)	C++14	37 / 100	2000 ms	31392 KB

match

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<int,ll> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<ll>::iterator sit;
typedef map<ll,ll>::iterator mit;
 
bool err;
string s;

void solve(int l, int r)
{
	if(l>r) return ;
	stack<char> S;
	string ans;
	int idx=-1;
	if(s[l]==s[r])
	{
		solve(l+1,r-1);
		if(err) return ;
		s[l]='('; s[r]=')';
		return ;
	}
	for(int i = r; i > l; i--)
	{
		if(!S.empty()&&S.top()==s[i])
		{
			S.pop();
		}
		else
		{
			S.push(s[i]);
		}
		if(s[l]==s[i-1]&&S.empty())
		{
			idx=i;
			break;
		}
	}
	if(idx<=l)
	{
		err=true;
		return ;
	}
	solve(l+1,idx-2);
	solve(idx,r);
	s[l]='('; s[idx-1]=')';
}
char a[100011];
int main()
{
	scanf("%s", a);
	int idx=0;
	while(a[idx]!='\0')
	{
		s+=a[idx];
		idx++;
	}
	solve(0,int(s.length())-1);
	if(err) cout<<-1<<'\n';
	else cout<<s<<'\n';	
}

Compilation message

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

Subtask #1

10.0 / 10.0

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

Subtask #2

27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	2116 KB	Output is correct
2	Correct	0 ms	2116 KB	Output is correct
3	Correct	0 ms	2116 KB	Output is correct
4	Correct	0 ms	2248 KB	Output is correct
5	Correct	0 ms	2248 KB	Output is correct
6	Correct	0 ms	2688 KB	Output is correct
7	Correct	0 ms	2376 KB	Output is correct

Subtask #3

0 / 63.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	2116 KB	Output is correct
2	Correct	0 ms	2116 KB	Output is correct
3	Correct	0 ms	2116 KB	Output is correct
4	Correct	0 ms	2248 KB	Output is correct
5	Correct	0 ms	2248 KB	Output is correct
6	Correct	0 ms	2688 KB	Output is correct
7	Correct	0 ms	2376 KB	Output is correct
8	Correct	3 ms	2248 KB	Output is correct
9	Correct	16 ms	3652 KB	Output is correct
10	Correct	6 ms	3276 KB	Output is correct
11	Correct	6 ms	4552 KB	Output is correct
12	Correct	136 ms	15864 KB	Output is correct
13	Correct	69 ms	17356 KB	Output is correct
14	Correct	766 ms	25140 KB	Output is correct
15	Correct	26 ms	28988 KB	Output is correct
16	Correct	26 ms	28992 KB	Output is correct
17	Correct	113 ms	29556 KB	Output is correct
18	Correct	19 ms	12860 KB	Output is correct
19	Correct	1379 ms	23252 KB	Output is correct
20	Correct	543 ms	21920 KB	Output is correct
21	Execution timed out	2000 ms	31392 KB	Execution timed out