ARTICLE AD BOX
In
(*b) |= ((*b) << m[i]);the ((*b) << m[i]) Performs a computation and needs to store the result somewhere, so it creates a temporary variable the only place that it is allowed to: automatic storage. The stack in this case. This temporary is just as big as its source bitset and overflows the stack.
Short version: *b is in dynamic storage, on the heap, but the result of ((*b) << m[i]) is not.
But the overflow is detected before executing any of the user code in main. How?
Modern compilers typically save time and effort adjusting the stack pointer as automatic variables go in and out of scope in a function by computing the worst case storage requirement at compile time and generating code that move the stack pointer only at the very beginning and very end of the function. The potential for overflow can be detected before any of the user code in the function is run. The program is more efficient, but the offending line of code is obscured.
How to approach a bizarre problem like this: Isolate it. Back up the code; copy it or use version control software. Remove everything that isn't needed to reproduce the problem.
Remove all of the unused headers. Compile and test to ensure the behaviour is the same.
The asker reports that no user input is taken by the program. So we remove it. We'll also take a educated gamble and remove all of the output. We also set the variables to known values. Since no input is taken, lets start with n = 1 to avoid undefined behavior indexing into an empty vector m at m[i] and w = 0 and see what happens.
#include<vector> #include<bitset> using namespace std; bitset<6250100> *b = new bitset<6250100>(); using ll = long long int; // not used. Also remove this. int main() { int n = 1, w = 0; vector<int>m(n); (*b) = 1; for (int i = 0; i < n; i++) { (*b) |= ((*b) << m[i]); } }Compile and test. We receive the same behavior, so we're on the right path.
Next we're going to remove as much as possible from the stack. If there's nothing on the stack, we can't overflow, right? Based on observations we should be proving this incorrect shortly. Since we're removing m, we need to replace m[i]. Good choices for replacement are 0 and 1, but any number should do. However a left shift of 0 can be compiled out as it does nothing, so we'll try that option last.
#include<bitset> using namespace std; bitset<6250100> *b = new bitset<6250100>(); int main() { (*b) = 1; for (int i = 0; i < 1; i++) { (*b) |= ((*b) << 1); } }Not much left, so this time I'll remove the for loop since it's hard coded to exactly 1 iteration.
#include<bitset> using namespace std; bitset<6250100> *b = new bitset<6250100>(); int main() { (*b) = 1; (*b) |= ((*b) << 1); }This code still overflows. Now we can either remove (*b) = 1; or (*b) |= ((*b) << 1);.
#include<bitset> using namespace std; bitset<6250100> *b = new bitset<6250100>(); int main() { (*b) = 1; }Does not overflow. Wrong choice. This makes sense as
#include<bitset> using namespace std; bitset<6250100> *b = new bitset<6250100>(); int main() { (*b) |= ((*b) << 1); }Overflows. This is where you'll probably have to stop and ask for help.
How do you fix this?
To keep going along this path you'll have to increase the size of the stack. 6250100 bits should be around 800000 bytes, close to the 1 MB default stack on a Windows system, so you shouldn't have to increase it much. Mind you, I don't do much Windows programming and there's a lot I didn't know. There might be another gotcha hidden in there.
It could also be you're expected to use a different algorithm that doesn't consume as much memory or you're expected to be using the GCC or clang compilers on a Linux desktop where the default stack size is typically 10 MB. If you are planning on doing much competition coding, I strongly recommend you do it on a Linux PC or virtual machine as this will be closer to what the judging computers are using.
