oj.uz

Submission #874918

# Submission time Handle Problem Language Result Execution time Memory
874918 2023-11-18T05:48:33 Z Muhammad_Aneeq Match (CEOI16_match) C++17
37 / 100
 2000 ms 1296 KB 
/*
بسم الله الرحمن الرحيم
Author:
                          (:Muhammad Aneeq:)
*/
#pragma GCC optimize("O2")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
string ans="";
string x;
int n;
map<char,vector<int>>d;
string g1="";
inline bool check(string s)
{
	string ans=string(n,' ');
	for (int i=0;i<s.size();i++)
	{
		ans[i]=s[i];
	}
	vector<int>q;
	bool w=(s.size()==2);
	for (int i=0;i<n;i++)
	{
		if (ans[i]!=' ')
		{
			if (ans[i]=='(')
			{
				q.push_back(x[i]);
			}
			else if (q.size())
				q.pop_back();
		}
		else
		{
			if (q.size()&&q.back()==x[i])
			{
				ans[i]=')';
				q.pop_back();
			}
			else
			{
				ans[i]='(';
				q.push_back(x[i]);
			}
		}
	}
	return (q.size()==0);
}
inline void solve()
{
	cin>>x;
	n=x.size();
	for (int i=0;i<n;i++)
		d[x[i]].push_back(i);
	for (auto i:d)
	{
		if (i.second.size()%2)
		{
			cout<<-1<<endl;return;
		}
		int z=0;
		for (auto j:i.second)
		{
			if (j%2)
				z++;
			else
				z--;
		}
		if (z)
		{
			cout<<-1<<endl;
			return;
		}
	}
	string ans="(";
	for (int i=1;i<n;i++)
	{

		if (check(ans+'('))
			ans+='(';
		else
			ans+=')';
	}
	cout<<ans<<endl;
}
int main()
{
  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
        solve();
}

Compilation message

match.cpp: In function 'bool check(std::string)':
match.cpp:22:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  for (int i=0;i<s.size();i++)
      |               ~^~~~~~~~~
match.cpp:27:7: warning: unused variable 'w' [-Wunused-variable]
   27 |  bool w=(s.size()==2);
      |       ^

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 3 ms 348 KB Output is correct
6 Correct 6 ms 348 KB Output is correct
7 Correct 10 ms 344 KB Output is correct

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 3 ms 348 KB Output is correct
6 Correct 6 ms 348 KB Output is correct
7 Correct 10 ms 344 KB Output is correct
8 Correct 134 ms 536 KB Output is correct
9 Correct 139 ms 348 KB Output is correct
10 Correct 115 ms 580 KB Output is correct
11 Correct 114 ms 600 KB Output is correct
12 Execution timed out 2033 ms 1296 KB Time limit exceeded
13 Halted 0 ms 0 KB -