Help me optimize my code

[AuJezus]

Hello this code right now is running in 1,1s with a lot of input (about 3 000 000 000 numbers i think). I don't know how much data I get to the code, because it's a tournament and I have no access to the input they give me. But I need it to be 1s or less. If you see any way to improve the speed please let me know. Sorry if my explanation is bad.

  #include <iostream>
#include <vector>

using namespace std;

int main()
{
	long a = 0;
	long suma = 0;
	long n;
	long allSum;
	vector<long> sums;
	vector<long> masyv;
	cin >> n;

	for (long i = 0; i < n - 1; i++)
	{
		long x;
		cin >> x;
		sums.push_back(x);
	}
	for (long i = 0; i < n; i++)
	{
		masyv.push_back(0);
	}
	cin >> allSum;

	masyv[n-1] = sums[0];

	for (long i = 1; i <= n - 2; i++)
	{
		masyv[i] = sums[i] - sums[0];
		a += 1;
	}

	for (long i = 1; i <= n - 1; i++)
	{
		suma += masyv[i];
	}

	masyv[0] = (allSum - suma) / a;
	masyv[n-1] = sums[0] - masyv[0];

	for (long i = 1; i <= n - 2; i++)
	{
		masyv[i] = sums[i] - masyv[n-1];
	}

	for (long i = 0; i < n; i++)
	{
		cout << masyv[i] << endl;
	}
}

[salem c]

You really need to post the question, not your answer.

Most competition problems are solved by first thinking about the problem and coming up with clever solutions that cut down massively on the amount of work needed to be done.

Not by coding the first thing that comes into your head, then wondering why it's too slow.

[dutch]

And if you're saying that it's possible n is as high as three billion, then that's going to take about 24 gigabytes to hold the sums vector and another 24 gigs to hold the masyv vector. And then you print out the entire masyv vector at the end! It's madness!

[jonnin]

just the first pass basic stuff.

the 'a' variable on line 33 is likely obtainable by i without the extra work.
the two for loops 30 and 36 can probably be combined. Just do an extra loop for the n-2 one so both run n-1 and toss the extra value you don't need (pad if you hit the end of a container).
the for loop on 44 may also fit into the original one, if you juggle some of the logic around**. so 3 for loops become one should cut the time by 50% or so.
push back is wrong, preallocate the size you need and access it directly.
and assuming the cout is redirected to a file, it won't take too long.

**you may need to 'seed' the vectors with the first 3 values out of the loops or something to get the loops to condense properly, but its totally worth it.

at some point you just have to wait. If you want to do billions of things, a second to process it may be acceptable. I think you can cut it to a fraction of that, maybe as low as 0.3 seconds or so, if you want to beat it to death, but you are trying to save fractions of a second by spending days of human time.

[seeplus]

Loop L22-25 isn't needed as the vector can be initialised in it's constructor.

For a first simple code opt (not algorithm), consider (not tried):

#include <vector>
#include <iostream>

using namespace std;

int main()
{
	long a {};
	long suma {};
	long n {};
	long allSum {};

	cin >> n;

	vector<long> sums(n);
	vector<long> masyv(n, 0);

	for (long i = 0; i < n - 1; ++i)
		cin >> sums[i];

	cin >> allSum;

	masyv[n - 1] = sums[0];
	a = n - 2;

	for (long i = 1; i <= n - 2; ++i) {
		masyv[i] = sums[i] - sums[0];
		suma += masyv[i];
	}

	suma += masyv[n - 1];
	masyv[0] = (allSum - suma) / a;
	masyv[n - 1] = sums[0] - masyv[0];

	for (long i = 1; i <= n - 2; ++i)
		masyv[i] = sums[i] - masyv[n - 1];

	for (long i = 0; i < n; i++)
		cout << masyv[i] << endl;
}