Help debugging AtCoder: Multiple of 2019

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!

You should try following the debugging tips mentioned here:

I’ve looked through that post, but the links to the debugging module don’t work–they give me a 404 error.

Thanks for noticing, should have been fixed by debugging redirects by bqi343 · Pull Request #3220 · cpinitiative/usaco-guide · GitHub.

I’ve followed all the steps on that page, but I’m still stuck. I don’t think it’s possible to download the test cases from AtCoder.

Actually, you can find their test cases at https://atcoder.jp/. But as the module mentions, you could always try generating your own test cases.

I’m looking through the testcases for that problem, and the only notable thing I can find about the ones I missed is that they are significantly larger than the ones I got correct. I changed all my ints to long longs to account for this, but I still have issues. When running testcases I generate by hand, the code gives the correct output.

Did you try writing a program to generate small test cases (as described in the module)?