ContestFucker's blog

By ContestFucker, history, 4 months ago, , Hi,

My solution gets WA in test case 10 and I think it because overflow but I can't see any overflow problem.

#include<bits/stdc++.h>
using namespace std;

const int INF = 1e9+7;

int MOD(int x){
return ((x%INF)+INF)%INF;
}

int main()
{
string n;cin >> n;
string s;
for(int i=0;i<n.size();++i){
if(n[i]=='a' || n[i]=='b') s+=n[i];
}
//Get number of all of the contigiuos 'a's
vector<int> ans;
int cnt = 0;
for(int i=0;i<s.size();++i){
if(s[i]=='a') ++cnt;
else{
ans.push_back(cnt);cnt=0;
}
}ans.push_back(cnt);
long long res=1;
for(auto &i : ans){
res = MOD(MOD(res) * MOD(i+1));
}cout << res-1;
} #c++, Comments (13)
 » Auto comment: topic has been updated by ContestFucker (previous revision, new revision, compare).
 » Auto comment: topic has been updated by ContestFucker (previous revision, new revision, compare).
 » Overflow in line res = MOD(MOD(res) * MOD(i+1)); $MOD(res) * MOD(i+1)$ might not fit in int limit (Can be of order (10 ^ 9) * (10 ^ 5))
•  » » How i can make it correct? I used unsigned long long it doesnt work.
•  » » » 4 months ago, # ^ | ← Rev. 2 →   Change the MOD function to accept ull instead of int
•  » » » » okay thanks can you tell me how exactly *1ll make things correct some times?
•  » » » » » 4 months ago, # ^ | ← Rev. 2 →   it casts integers it is multiplied with to long long datatype (biggest datatype)
•  » » » » » » 4 months ago, # ^ | ← Rev. 2 →   we cannot simply use (long long)?
•  » » » » » » » i'm pretty sure you can but 1LL is more convenient often
•  » » » » » » » » Thank you
•  » » » Your AC code.
•  » » » » Thank you can you tell me how 1ll work?
•  » » » » » 4 months ago, # ^ | ← Rev. 3 →   That's not needed since we kept long long int as datatype of res. If that is not the case multiplying by 1ll promotes the type of integer to long long int (according to normal rules of type promotion (casting) thereby helping us avoid overflows in this case)Edit : Ok it will be needed since you return int in the MOD function.