Submission #99611

#	Time	Username	Problem	Language	Result	Execution time	Memory
99611		igzi	parentrises (BOI18_parentrises)	C++17	72 / 100	139 ms	10248 KiB

parentrises

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

using namespace std;

int p,t,i,m,l,d,res[31];

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);
}

string resi(string s){
int i;
u.clear();
v.clear();
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()) ans="impossible";
return ans;
}

int main(){
std::ios_base::sync_with_stdio(false);
int a[30]={158331292,79165646,39237478,19865414,9932707,4906266,2496396,1248198,613440,314472,157236,76680,39768,19884,9578,5062,2531,1194,652,326,148,86,43,18,12,6,2,2,1,0};
cin>>p;
cin>>t;
if(p==1){
while(t--){
cin>>s;
cout<<resi(s)<<endl;
}
}
else{
int n;
while(t--){
cin>>n;
cout<<a[30-n]<<endl;
}
}
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 'std::__cxx11::string resi(std::__cxx11::string)':
parentrises.cpp:43:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(i=0;i<s.size();i++){
         ~^~~~~~~~~
parentrises.cpp:56:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(i=0;i<v.size();i++){
         ~^~~~~~~~~
parentrises.cpp:63:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(i=0;i<u.size();i++){
         ~^~~~~~~~~
parentrises.cpp:64: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: 6 / 6
• Subtask 6: 16 / 16
• Subtask 7: 0 / 28