bad_alloc() problem

[reach devi]

Hi all,
I was trying to solve one of the google code jam problems. I encountered with an error and need some help.The following code that i wrote for a particular problem is not working at all.The code compiles but shows a runtime error something like : "throwing an instance of std::bad_alloc()" . Can anyone help me out please? here is the code.

#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>

using namespace std;

int main(){
  ofstream fout("ms.in");
  ifstream fin("ms.out");
  int T,x=1,n,Y,num=0;
  fin >> T;
  fout << T << endl;
  for(x=1;x<T+1;x++){
    vector<int> v1(10,0),v2(10,0);
	fin >> n;
	fout << n << endl;
	for(int i=0;i<n;i++){
	  fin >> num;
	  v1.push_back(num);
	}
	for(int i=0;i<n;i++){
	  fin >> num;
	  v2.push_back(num);
	}
	sort(v1.begin(),v1.end());
	sort(v2.begin(),v2.end());
	int i,j;
	for(i=0,j=n-1;i<v1.size();i++,j--)
	  Y+=v1[i]*v2[j];
	fout << "case #" << x << ": " << Y << endl;
  }
  return 0;
}

[Ispil]

Compiled fine on the shell.

[reach devi]

@Ispil I am using windows.And the code is compiling fine.but not running.
Its showing a run time error.Is compiling on shell somewhat different from compiling on windows?I really don't know anything about it...

[Ganado]

No, you're right, the problem here shouldn't have to do with compilation. The text inside your ms.in and ms.out files may be the source of the problems.

I would check to make sure they open properly first off, and use a debugger to see where exactly it's throwing the exception.

[MiiNiPaa]

How large is ms.in file? Can you post it somewhere?

[reach devi]

@Ganado thank you very much.you can check the the ms.in and ms.out in google code jam's website.The question is named as minimum scalar product. The names of files are different although.It is named A-small-practice.in

@MiiNiPaa I am posting my ms.in file below.please check.

2
3
1 3 -5
-2 4 1
5
1 2 3 4 5
1 0 1 0 1

[MiiNiPaa]

Did yoiu really mean to read from .out file and write to .in file?

Some other hints:
You have 10 zeroes in each vector which is not what you want.
int is too small to hold all possible values.
You are outputting extra information in your file.

[reach devi]

@MiiNiPaa Thank you for pointing out the error.The .out file and .in file were in wrong position.so i changed it.i have commented out the extra information.but i am getting right answer for first iteration and a wrong answer for the next one.
Can you help in correcting it? Here is the code now.

#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>

using namespace std;

int main(){
  ofstream fout("ms.out");
  ifstream fin("ms.in");
  int T,x=1,n,Y,num=0;
  fin >> T;
  //fout << T << endl;
  for(x=1;x<T+1;x++){
    vector<int> v1,v2;
	fin >> n;
	//fout << n << endl;
	for(int i=0;i<n;i++){
	  fin >> num;
	  v1.push_back(num);
	}
	for(int i=0;i<n;i++){
	  fin >> num;
	  v2.push_back(num);
	}
	sort(v1.begin(),v1.end());
	sort(v2.begin(),v2.end());
	int i,j;
	for(i=0,j=n-1;i<v1.size();i++,j--)
	  Y+=v1[i]*v2[j];
	fout << "case #" << x << ": " << Y << endl;
  }
  return 0;
}

[MiiNiPaa]

Well, your logic is wrong. Rethink your approach.

Now you are multiplying following:

1 2 3 4 5
0 0 1 1 1

3+4+5 == 12

Actually first iteration should nit give correct answer (-25) either

[reach devi]

But according to line 29 and 30 of the second code,it should work as follows:

1 2 3 4 5
0 0 1 1 1
3 + 2 + 1==6

Is declaring vectors inside the loop is affecting my solution?

[MiiNiPaa]

What the initial value of Y? What happens to Y after loop iteration ends?

[reach devi]

Ya got your point.and yes got the right answer now.Thank you very much...
Have a nice day to you MiiNiPaa

[MiiNiPaa]

Just for gun I decided to rewrite your code in C++14:

#include <algorithm>
#include <fstream>
#include <iterator>
#include <numeric>
#include <vector>


int main()
{
    constexpr int reservation_size = 1000;
    std::ifstream  fin("A-large-practice.in");
    std::ofstream fout("ms.out");
    unsigned amount;
    fin >> amount;
    for(unsigned Case = 1; Case <= amount; ++Case) {
        std::vector<long long> v1; v1.reserve(reservation_size);
        std::vector<long long> v2; v2.reserve(reservation_size);
        unsigned vector_size;
        fin >> vector_size;
        std::copy_n(std::istream_iterator<long long>(fin), vector_size, std::back_inserter(v1));
        std::copy_n(std::istream_iterator<long long>(fin), vector_size, std::back_inserter(v2));
        std::sort(v1.begin(),v1.end());
        std::sort(v2.begin(),v2.end(), std::greater<>());
        long long y = std::inner_product(v1.begin(), v1.end(), v2.begin(), 0LL);
        fout << "Case #" << Case << ": " << y << '\n';
    }
}

[reach devi]

thank you.My code passed the small input.But it is not passing the large input test.I am also using long long in my vector.Can you tell me what changes i have to do to my code? I am using c++ 11

[MiiNiPaa]

Check every place input goes: mainly your Y and num vairables.

[reach devi]

thank you again...@MiiNiPaa. Changed the type of Y and num.And the solution was accepted.:)