Submission #95952

#	Time	Username	Problem	Language	Result	Execution time	Memory
95952		igzi	parentrises (BOI18_parentrises)	C++17	50 / 100	112 ms	8200 KiB

parentrises

#include <bits/stdc++.h>
#define maxN 1000005

using namespace std;

int p,t,i,m,l,d;

string s,ans;

vector <int> v,u;

bool moze(int m){
int x;
x=m+v.size()-u.size();
if(x<=0) return true;
if(x>u.size() || v[m-1]>u[u.size()-x]) return false;
return true;
}

bool proveri(){
int r,b,i;
r=b=0;
for(i=0;i<s.size();i++){
if(s[i]=='('){
if(ans[i]=='G') {r++; b++;}
if(ans[i]=='R') r++;
if(ans[i]=='B') b++;
}
else{
if(ans[i]=='G') {r--; b--;}
if(ans[i]=='R') r--;
if(ans[i]=='B') b--;
if(r<0 || b<0) return false;
}
}
return (r==0 && b==0);
}

int main(){
std::ios_base::sync_with_stdio(false);
cin>>t;
cin>>t;
while(t--){
cin>>s;
for(i=0;i<s.size();i++){
if(s[i]=='(') v.push_back(i);
else u.push_back(i);
}
l=0;
d=v.size();
while(d>l){
m=(l+d)/2+1;
if(moze(m)) l=m;
else d=m-1;
}
ans=s;
d=l+v.size()-u.size();
for(i=0;i<v.size();i++){
if(i<l)  ans[v[i]]='G';
else{
if((i-l)%2) ans[v[i]]='R';
else ans[v[i]]='B';
}
}
for(i=0;i<u.size();i++){
if(i>=u.size()-d) ans[u[i]]='G';
else{
if(i%2) ans[u[i]]='R';
else ans[u[i]]='B';  
}
}
if(proveri()) cout<<ans<<endl;
else cout<<"impossible"<<endl;
v.clear();
u.clear();
}
return 0;
}

Compilation message (stderr)

parentrises.cpp: In function 'bool moze(int)':
parentrises.cpp:16:5: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 if(x>u.size() || v[m-1]>u[u.size()-x]) return false;
    ~^~~~~~~~~
parentrises.cpp: In function 'bool proveri()':
parentrises.cpp:23:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(i=0;i<s.size();i++){
         ~^~~~~~~~~
parentrises.cpp: In function 'int main()':
parentrises.cpp:45:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(i=0;i<s.size();i++){
         ~^~~~~~~~~
parentrises.cpp:58:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(i=0;i<v.size();i++){
         ~^~~~~~~~~
parentrises.cpp:65:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(i=0;i<u.size();i++){
         ~^~~~~~~~~
parentrises.cpp:66:5: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 if(i>=u.size()-d) ans[u[i]]='G';
    ~^~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 6 / 6
• Subtask 4: 28 / 28
• Subtask 5: 0 / 6
• Subtask 6: 0 / 16
• Subtask 7: 0 / 28