aksinghal_29's blog

By aksinghal_29, history, 5 years ago, In English

Question Link :- E. K-periodic Garland

My Solution is here ```

#include <climits>
#include<iostream>
#include<bits/stdc++.h>
#include<algorithm>
#include<queue>
#include <vector>
#define ll long long int 
using namespace std;
int main(){
 ll t;
 cin>>t;
 while(t--){
     ll n,k;
     cin>>n>>k;
     string s ;
     cin>>s;
     //cout<<"s="<<s<<" k"<<k<<endl;
     vector<char> dp[k];
     ll i;
     ll total=0;
     for(i=0;i<n;i++){
         if(s[i]=='1'){
             total++;
         }
        dp[i%k].push_back(s[i]);
     }
     ll min1=INT_MAX;
    for(i=0;i<k;i++){
        string ansString="";
        string mainAns="";
        ll j;
        for(j=0;j<dp[i].size();j++){
            if(dp[i][j]=='0'&&ansString.length()==0){
                continue;
        } 
        else{
            ansString=ansString+dp[i][j];
        }
    }
    //cout<<"ansString"<<ansString<<endl;
    for(ll kk=ansString.length()-1;kk>=0;kk--){
            if(ansString[kk]=='0'&& mainAns.length()==0){
                continue;
            } 
            else{
               // cout<<ansString[kk]<<" ";
                mainAns=ansString[kk]+mainAns;
            }
        }
    //cout<<"mainAns"<<mainAns<<endl;
    ll totalCount = count(dp[i].begin(),dp[i].end(),'1');
   // cout<<"totalCount"<<totalCount<<endl;
    ll minReq = mainAns.length()-2*totalCount+total;
    if(minReq<min1){
        min1=minReq;
    }
 }
cout<<min1<<endl;
}
}

``` I confused why i got TLE but codeforces

  • Vote: I like it
  • -10
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by aksinghal_29 (previous revision, new revision, compare).

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Try using fast io

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For line for(ll kk=ansString.length()-1;kk>=0;kk--),

it should be for(int kk=ansString.length()-1;kk>=0;kk--)

But it gives WA on test 2.80291378

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    but why this difference between ll or int

    And thanks for help

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      See the comments below the blog. Link

      In a nutshell, it's expensive to use long long to do some simple caculation.

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Sum of two strings works in linear time. If you want to push back a string use operator+=.