oj.uz

Submission #874908

# Submission time Handle Problem Language Result Execution time Memory
874908 2023-11-18T05:16:35 Z Muhammad_Aneeq Match (CEOI16_match) C++17
10 / 100
 15 ms 348 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)
{
	map<char,pair<int,int>>z;
	map<char,bool>g;
	string ans=string(n,' ');
	for (int i=0;i<s.size();i++)
	{
		ans[i]=s[i];
		if (ans[i]=='(')
			z[x[i]].first++;
		else
			z[x[i]].second++;
	}
	bool w=(s.size()==7);
	for (int i=s.size();i<x.size();i++)
	{
		if (g[x[i]]==1||(z[x[i]].first>=d[x[i]].size()/2))
		{
			ans[i]=')';
			z[x[i]].second++;
		}
		else
		{
			ans[i]='(';
			z[x[i]].first++;
		}
		g[x[i]]^=1;
	}
	vector<char>q;
	for (int i=0;i<n;i++)
	{
		if (ans[i]==')')
		{
			if (q.size()==0)
				return 0;
			if (q.back()!=x[i])
				return 0;
			q.pop_back();
		}
		else
			q.push_back(x[i]);
	}
	if (q.size()==0)
	{
		if (g1=="")
			g1=ans;
		g1=min(ans,g1);
	}
	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:24:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |  for (int i=0;i<s.size();i++)
      |               ~^~~~~~~~~
match.cpp:33:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  for (int i=s.size();i<x.size();i++)
      |                      ~^~~~~~~~~
match.cpp:35:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   if (g[x[i]]==1||(z[x[i]].first>=d[x[i]].size()/2))
match.cpp:32:7: warning: unused variable 'w' [-Wunused-variable]
   32 |  bool w=(s.size()==7);
      |       ^

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
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 Incorrect 15 ms 344 KB Output isn't correct
5 Halted 0 ms 0 KB -

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 Incorrect 15 ms 344 KB Output isn't correct
5 Halted 0 ms 0 KB -