Submission #932484

# Submission time Handle Problem Language Result Execution time Memory
932484 2024-02-23T13:41:45 Z pcc parentrises (BOI18_parentrises) C++14
0 / 100
1 ms 600 KB
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>


void solve(){
	string s;
	cin>>s;
	vector<int> v[2];
	for(int i = 0;i<s.size();i++){
		v[s[i] == ')'].push_back(i);
	}
	string ans = s;
	reverse(v[1].begin(),v[1].end());
	bool flag = true;
	if(v[0].size()>v[1].size()){
		int pr = v[0].size()-v[1].size(),pl = 0;
		if(pr>v[1].size()){
			cout<<"impossible\n";
			return;
		}
		while(pr<v[1].size()&&pl<v[0].size()&&v[1][pr]>v[0][pl])pl++,pr++;
		for(int i = 0;i<pr;i++)ans[v[1][i]] = 'G';
		for(int i = 0;i<pl;i++)ans[v[0][i]] = 'G';
	}
	else{
		int pl = v[1].size()-v[0].size(),pr = 0;
		if(pl>v[0].size()){
			cout<<"impossible\n";
			return;
		}
		while(pl<v[0].size()&&pr<v[1].size()&&v[1][pr]>v[0][pl])pl++,pr++;
		for(int i = 0;i<pr;i++)ans[v[1][i]] = 'G';
		for(int i = 0;i<pl;i++)ans[v[0][i]] = 'G';
	}
	pii cnt = {0,0};
	for(int i = 0;i<ans.size();i++){
		if(s[i] == '('){
			if(ans[i] == 'G')cnt.fs++,cnt.sc++;
			else{
				if(cnt.fs>cnt.sc)cnt.sc++,ans[i] = 'B';
				else cnt.fs++,ans[i] = 'R';
			}
		}
		else{
			if(ans[i] == 'G')cnt.fs--,cnt.sc--;
			else{
				if(cnt.fs>cnt.sc)cnt.fs--,ans[i] = 'R';
				else cnt.sc--,ans[i] = 'B';
			}
		}
		if(cnt.fs<0||cnt.sc<0){
			flag = false;
		}
	}
	if(cnt.fs||cnt.sc)flag = false;
	cout<<(flag?ans:"impossible")<<'\n';
	return;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t;cin>>t;
	while(t--)solve();
}
/*
()()()
*/

Compilation message

parentrises.cpp: In function 'void solve()':
parentrises.cpp:16:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |  for(int i = 0;i<s.size();i++){
      |                ~^~~~~~~~~
parentrises.cpp:24:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |   if(pr>v[1].size()){
      |      ~~^~~~~~~~~~~~
parentrises.cpp:28:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |   while(pr<v[1].size()&&pl<v[0].size()&&v[1][pr]>v[0][pl])pl++,pr++;
      |         ~~^~~~~~~~~~~~
parentrises.cpp:28:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |   while(pr<v[1].size()&&pl<v[0].size()&&v[1][pr]>v[0][pl])pl++,pr++;
      |                         ~~^~~~~~~~~~~~
parentrises.cpp:34:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |   if(pl>v[0].size()){
      |      ~~^~~~~~~~~~~~
parentrises.cpp:38:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |   while(pl<v[0].size()&&pr<v[1].size()&&v[1][pr]>v[0][pl])pl++,pr++;
      |         ~~^~~~~~~~~~~~
parentrises.cpp:38:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |   while(pl<v[0].size()&&pr<v[1].size()&&v[1][pr]>v[0][pl])pl++,pr++;
      |                         ~~^~~~~~~~~~~~
parentrises.cpp:43:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |  for(int i = 0;i<ans.size();i++){
      |                ~^~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 512 KB Unexpected end of file - token expected
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 512 KB Unexpected end of file - token expected
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 512 KB Unexpected end of file - token expected
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 600 KB Expected integer, but "impossible" found
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 600 KB Expected integer, but "impossible" found
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 600 KB Expected integer, but "impossible" found
2 Halted 0 ms 0 KB -