What is wrong with the solution to this problem

Question

I am trying to solve: https://www.spoj.com/problems/ANARC05B/

I am using Binary Search to solve this problem. I think I have followed the correct approach. Can anybody help me with a test case that would fail?

Below is my code, it passes on the sample test cases, i dont see a problem with my code but still not sure why i get WA!! Please help!!

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
using namespace std;

int BinarySearch(vector<int> arr, int key)
{
    int minNum = 0;
    int maxNum = arr.size() - 1;

    while (minNum <= maxNum)
    {
        int mid = (minNum + maxNum) / 2;
        if (key == arr[mid])
        {
            return mid;
        }
        else if (key < arr[mid])
        {
            maxNum = mid - 1;
        }
        else
        {
            minNum = mid + 1;
        }
    }
    return -1;
}

signed long Solve(vector<int> First, vector<int> Second)
{

    // Find the intersections in both the arrays and store the indices for them.
    vector<int> FirstInterIndices;
    vector<int> SecondInterIndices;
    for (int i = 0; i < Second.size(); i++)
    {
        int idx = BinarySearch(First, Second[i]);
        if (idx != -1)
        {
            SecondInterIndices.push_back(i);
            FirstInterIndices.push_back(idx);
        }
    }

    if (FirstInterIndices.empty())
    {
        FirstInterIndices.push_back(FirstInterIndices.size() - 1);
        SecondInterIndices.push_back(SecondInterIndices.size() - 1);
    }
    //Find Intersections ends

    //Calc the sum upto intersections in both the arrays and store them
    vector<signed long> FirstInterSum;
    vector<signed long> SecondInterSum;

    for (int i = 0; i < SecondInterIndices.size(); i++)
    {
        int k = 0;
        signed long Sum = 0;
        if (i > 0)
        {
            k = SecondInterIndices[i - 1] + 1;
        }
        for (; k <= SecondInterIndices[i]; k++)
        {
            Sum += (signed long)Second[k];
        }
        SecondInterSum.push_back(Sum);
    }
    signed long SumLeft = 0;
    if (SecondInterIndices.size() > 0)
    {
        for (int k = SecondInterIndices[SecondInterIndices.size() - 1] + 1; k < Second.size(); k++)
        {
            SumLeft += (signed long)Second[k];
        }
        SecondInterSum.push_back(SumLeft);
    }


    for (int i = 0; i < FirstInterIndices.size(); i++)
    {
        int k = 0;
        signed long Sum = 0;
        if (i > 0)
        {
            k = FirstInterIndices[i - 1] + 1;
        }
        for (; k <= FirstInterIndices[i]; k++)
        {
            Sum += (signed long)First[k];
        }
        FirstInterSum.push_back(Sum);
    }

    if (FirstInterIndices.size() > 0)
    {
        SumLeft = 0;
        for (int k = FirstInterIndices[FirstInterIndices.size() - 1] + 1; k < First.size(); k++)
        {
            SumLeft += (signed long)First[k];
        }
        FirstInterSum.push_back(SumLeft);
    }
    // Calc sum upto intersections ENDs

    // Compare corresponding elements (sum upto intersections) and add the max from First and Second
    signed long MaxSum = 0;
    int j = 0;
    for (; j < FirstInterSum.size(); j++)
    {
        if (j < SecondInterSum.size())
        {
            if (FirstInterSum[j] > SecondInterSum[j])
            {
                MaxSum += FirstInterSum[j];
            }
            else
            {
                MaxSum += SecondInterSum[j];
            }
        }
    }

    // If Any sum exists after last intersection add that as well.
    if (j < FirstInterSum.size())
    {
        MaxSum += FirstInterSum[FirstInterSum.size() - 1];
    }
    if (j < SecondInterSum.size())
    {
        MaxSum += SecondInterSum[SecondInterSum.size() - 1];
    }
    return MaxSum;
}

vector<int> getArray()
{
    vector<int> res;
    int n;
    cin >> n;
    int x;
    for (int i = 0; i < n; i++)
    {
        cin >> x;
        res.push_back(x);
    }
    return res;
}

int main()
{
    for (;;)
    {
        vector<int> First = getArray();
        if (First.size() == 0)
            return 0;
        vector<int> Second = getArray();
        cout << Solve(First, Second);
    }
    return 0;
}

Answer 1

You get WA because the output format is incorrect. I ran your code, and the output looks like this:

13 3 5 7 9 20 25 30 40 55 56 57 60 62
11 1 4 7 11 14 25 44 47 55 57 100
4 -5 100 1000 1005
3 -12 1000 1001
0450
2100
Program ended with exit code: 0

but the expected format should be:

13 3 5 7 9 20 25 30 40 55 56 57 60 62
11 1 4 7 11 14 25 44 47 55 57 100
4 -5 100 1000 1005
3 -12 1000 1001
0
450
2100
Program ended with exit code: 0

difference is 0 and 450 are not on the same line.