oj.uz

Submission #874917

# Submission time Handle Problem Language Result Execution time Memory
874917 2023-11-18T05:47:21 Z Muhammad_Aneeq Match (CEOI16_match) C++17
37 / 100
 2000 ms 1656 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="";
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]);
			}
		}
	}
	// if (w)
	// 	cout<<ans<<endl;
	if (q.size()==0)
	{
		if (g1=="")
			g1=ans;
		g1=min(g1,ans);
	}
	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<<g1<<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 5 ms 460 KB Output is correct
5 Correct 3 ms 348 KB Output is correct
6 Correct 6 ms 468 KB Output is correct
7 Correct 11 ms 348 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 5 ms 460 KB Output is correct
5 Correct 3 ms 348 KB Output is correct
6 Correct 6 ms 468 KB Output is correct
7 Correct 11 ms 348 KB Output is correct
8 Correct 126 ms 344 KB Output is correct
9 Correct 136 ms 600 KB Output is correct
10 Correct 119 ms 852 KB Output is correct
11 Correct 111 ms 608 KB Output is correct
12 Execution timed out 2033 ms 1656 KB Time limit exceeded
13 Halted 0 ms 0 KB -