ContestFucker's blog

By ContestFucker, history, 4 months ago, In English,

Hi,

Problem ==> http://codeforces.com/problemset/problem/1084/C

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);
    //Calculate the answer
    long long res=1;
    for(auto &i : ans){
        res = MOD(MOD(res) * MOD(i+1));
    }cout << res-1;
}
 
 
 
 
  • Vote: I like it
  • -1
  • Vote: I do not like it

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How i can make it correct? I used unsigned long long it doesnt work.

    • »
      »
      »
      4 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Change the MOD function to accept ull instead of int

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Your AC code.

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thank you can you tell me how 1ll work?

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
          Rev. 3   Vote: I like it 0 Vote: I do not like it

          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.