Submission #489400

#	Time	Username	Problem	Language	Result	Execution time	Memory
489400		MarkoDimi3c	Election (BOI18_election)	C++14	0 / 100	6 ms	204 KiB

election

#include<bits/stdc++.h>

using namespace std;

int main(){

int n;
cin >>n;
vector<char> v(n);
vector<int> t;
vector<int> c;
int tt=0;
int tc=0;
bool proslit = false;
bool proslic = false;
cin >> v[0];

if(v[0] == 'T'){
    proslit=true;
    tt++;
}
else{
    proslic=true;
    tc++;
}
bool prvitony = proslit;
for(int i = 1; i < n; i++){
        cin>>v[i];
        if(v[i]=='T'){
            if(proslit == true){
                tt++;
            }
            else{
                if(tt >0)t.push_back(tt);
                tt=1;
            }
            proslic=false;
            proslit=true;
        }
        else{
          if(proslic == true){
                tc++;
            }
            else{
                if(tc>0)c.push_back(tc);
                tc=1;
            }
            proslit=false;
            proslic=true;
        }

}
c.push_back(tc);
 t.push_back(tt);


vector<int> g;
if(prvitony){
    g.push_back(t[0]);
    g.push_back(c[0]+g[0]);
    for(int i = 1; i < c.size();i++){
        g.push_back(t[i]+g[2*i]);
        g.push_back(c[i]+g[2*i+1]);
    }
    if(t.size()>c.size())g.push_back(t[t.size()-1]+g[g.size()-1]);
}
else{
     g.push_back(c[0]);
    g.push_back(t[0]+g[0]);
    for(int i = 1; i < t.size();i++){
        g.push_back(c[i]+g[2*i]);
        g.push_back(t[i]+g[2*i+1]);
    }
    if(c.size()>t.size())g.push_back(c[c.size()-1]+g[g.size()-1]);
}

int q;
cin >> q;
int l,r;
while(q--){
    cin >> l >> r;
    vector<int>izt;
    int u = 0;
    int i = 0;
    while(g[i]<l){
        u++;
        i++;
        if(i==g.size())break;
    }
    i=0;
    int e = 0;
    while(g[i]<=r){
        e++;
        i++;
        if(i==g.size())break;
    }
    int lint = g[u]-l+1;
    int rint = r-g[e-1];
    bool toni;
    if(prvitony){
        if(u%2 == 0)toni=true;
        else toni = false;
    }
    else{
        if(u%2 == 0)toni = false;
        else toni = true;
    }
    int tony = 0;
    int cap = 0;
    if(toni)izt.push_back(lint);
    else cap+=lint;
    toni=!toni;
    for(int i =u+1; i < e;i++){
        if(!toni){
            toni=!toni;
            cap+=g[i]-g[i-1];
        }
        else{
            if(tony+g[i]-g[i-1] <= cap){
                tony+=g[i]-g[i-1];
                izt.push_back(0);
            }
            else{
                izt.push_back(g[i]-g[i-1]-cap+tony);
                tony+=cap-tony;
            }
            toni=!toni;
        }
    }
    if(toni){
        if(tony+rint <= cap){
                tony+=rint;
                izt.push_back(0);
            }
            else{
                izt.push_back(rint-cap+tony);
                tony+=cap-tony;
            }
    }
    tony=0;
    cap=0;
    int j = 1;
    if(toni){
            izt[izt.size()-j]=max(izt[izt.size()-j],rint);
            j++;
    }
    else cap+=rint;
    toni=!toni;
    for(int i =e-1; i > u;i--){
        if(!toni){
            toni=!toni;
            cap+=g[i]-g[i-1];
        }
        else{
            if(tony+g[i]-g[i-1] <= cap){
                tony+=g[i]-g[i-1];
            }
            else{
                izt[izt.size()-j]=max(izt[izt.size()-j],g[i]-g[i-1]-cap+tony);
                tony+=cap-tony;
            }
            j++;
            toni=!toni;
        }
    }
    if(toni){
        if(tony+lint <= cap){
                tony+=lint;
            }
            else{
                izt[izt.size()-j]=max(izt[izt.size()-j], lint-cap+tony);
                tony+=cap-tony;
            }
    }
    int h = 0;
    for(int i = 0; i < izt.size();i++)h+=izt[i];
    cout << h << endl;
}
return 0;
}

Compilation message (stderr)

election.cpp: In function 'int main()':
election.cpp:61:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for(int i = 1; i < c.size();i++){
      |                    ~~^~~~~~~~~~
election.cpp:70:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for(int i = 1; i < t.size();i++){
      |                    ~~^~~~~~~~~~
election.cpp:88:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |         if(i==g.size())break;
      |            ~^~~~~~~~~~
election.cpp:95:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |         if(i==g.size())break;
      |            ~^~~~~~~~~~
election.cpp:176:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  176 |     for(int i = 0; i < izt.size();i++)h+=izt[i];
      |                    ~~^~~~~~~~~~~~

• Subtask 1: 0 / 28
• Subtask 2: 0 / 54
• Subtask 3: 0 / 18