My Work
//Atcoder: Multiple of 2019
//https://atcoder.jp/contests/abc164/tasks/abc164_d
//5 correct, 6 wrong answer. All within time limit.
#include<bits/stdc++.h>
using namespace std;
int main() {
string s1; cin>>s1;
int n=s1.size();
//Store the string S in a vector of integers, in reverse order
vector<int>s;
for(int j=n-1; j>=0; j--) {
s.push_back(s1[j]-48); //convert from char to int (ascii)
}
/*
Approach: input number=sum of s[i]*10^i for 0<=i<=n-1. Keep a prefix array where
prefix_s[k]=(s[0]*10^0+s[1]*10^1+...+s[k]*10^k)%2019.
(Essentially, the last k digits of the input number mod 2019.)
Also maintain a map where each value mod 2019 is mapped
to the number of times it appears in prefix_s.
Then use a variation on the cses_subarraysums2.cpp trick.
For (i,j) to work where i and j are as defined in the problem,
we must have (prefix_s[j-1]-prefix_s[i-1])%2019=0. This is because
the prefix_s[j-1]-prefix_s[i-1] will give the desired substring*10^x
for some x, and since 10^x cannot be congruent to 0 mod 2019, we must have
desired substring%2019=0. So, their difference only needs to be a multiple of
2019.
cses_subarraysums2: Traverse the array, adding to the sum as we pass each element.
As we pass each element, check if the sum is equal to x. Add the current
sum to a map containing all previous sums mapped to the number of times
they occurred. Add past_sums[current_sum] to answer.
*/
//Set up prefix array/vector
int prefix_s[n];
prefix_s[0]=s[0];
for(int j=1; j<n; j++) {
long long next=prefix_s[j-1]+s[j]*pow(10,j);
prefix_s[j]=(next)%2019;
}
int ans=0;
map<int,int> past_nums;
past_nums[0]=1;
for(int j=0; j<n; j++) {
ans+=past_nums[prefix_s[j]];
past_nums[prefix_s[j]]++;
}
cout << ans << "\n";
}
I’m aware that my code is correct in terms of logic, and it also runs fast enough. However, it misses test cases 11-12 and 14-17 despite running well within the time limit. Initially I suspected that I needed to change some of the ints to long longs, but it still gives the same results. Can anyone help? Thanks!