Why am I getting a 'Runtime Error - SIGSEGV' in my code?

Question

I have got some impossible queries for you! (or are they? ;) )

You have n binary numbers of length m. The i^th binary number is B_i. Also, you have to perform q queries on them. The indexing is zero-based and the indexing of bits starts from left.

The queries are of type : a, i, j.
If a is:

0 : perform Logical AND operation between B_i and B_j and output the number of 1s in the result.
1 : perform Logical OR operation between B_i and B_j and output the number of 1s in the result.
2 : perform Logical XOR operation between B_i and B_j and output the number of 1s in the result.
3 : flip the value of the j^th bit of B_i (i.e. set the bit to 0 if it equals 1 and vice-versa).

Note: For queries of type 0, 1, and 2, the binary numbers remain unchanged.

It is also recommended to use Fast I/O for C++ and JAVA programmers.

Input Format:

First line contains Integers n and m.
The next n lines contain binary numbers of length m.
The i^th line contains binary number B_i.
The next line contains an integer q
The next q lines contain queries of type : a, i, j.

Output Format:

Output number of 1s in the result of type 0, 1 and 2 queries.

Constraints:
1<=n, m<=2500
1<=q<=10^6

I have tried changing the array size, but still the error remains the same!

#include <iostream>
#include <math.h>
#include <bits/stdc++.h>
using namespace std;


int main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,m;
    cin>>n>>m;
    char arr[3000][3000];

    for(int i=0;i<n;i++)
    for(int j=0;j<m;j++)
    {
        cin>>arr[i][j];
    }


    long int q;
    cin>>q;
    char query[3000][3000];
    for(long int k=0;k<q;k++)
    for(long int l=0;l<3;l++)
    {
        cin>>query[k][l];
    }


    for(long int i=0;i<q;i++)
    {
        if(int(query[i][0]-48)==3)
        {
            if(arr[int(query[i][1])-48][int(query[i][2])-48]=='1')
            {
                arr[int(query[i][1])-48][int(query[i][2])-48]='0';
            }
            else
            {
                arr[int(query[i][1])-48][int(query[i][2])-48]='1';
            }
        } 

        else if(int(query[i][0]-48)==2)
        {
            int cntr=0;
            int bi=int(query[i][1])-48;
            int bj=int(query[i][2])-48;

            for(int i=0;i<m;i++)
            {
                int xorres=arr[bi][i]^arr[bj][i];
                if(xorres==1)
                cntr++;
            }
            cout<<cntr<<endl;
        }

        else if(int(query[i][0]-48)==1)
        {
            int cntr=0;
            int bi=int(query[i][1])-48;
            int bj=int(query[i][2])-48;

            for(int i=0;i<m;i++)
            {
                int andres=arr[bi][i]|arr[bj][i];
                if(andres-48==1)
                cntr++;
            }
            cout<<cntr<<endl;

        }

        else if(int(query[i][0]-48)==0)
        {
            int cntr=0;
            int bi=int(query[i][1])-48;
            int bj=int(query[i][2])-48;

            for(int i=0;i<m;i++)
            {
                int andres=arr[bi][i]&arr[bj][i];
                if(andres-48==1)
                cntr++;
            }
            cout<<cntr<<endl;

        }
    }



    return 0;
}

Local variables (including arrays) are placed on the stack by compilers. The stack is a limited resource, on e.g. Linux it's 8MiB. Now think about the array `arr`... How much space does it need? How much space is needed for both `arr` *and* `query` together? Time to learn about [`std::vector`](https://en.cppreference.com/w/cpp/container/vector). And [get a few good books](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list/388282#388282) as well. Online judge/competition sites are really bad for beginners. — Some programmer dude, Aug 12 '19 at 13:37
Also, the standard: [Don't include bits/stdc++.h](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h), and [don't use `using namespace std;`](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice). — Frodyne, Aug 12 '19 at 13:44
You don't need to store all the queries before processing them. Do one at a time. Use a vector of vectors for the inputs. (Or a static array, if you absolutely must use an array.) — molbdnilo, Aug 12 '19 at 13:44
Also, `'0'` is both portable and comprehensible; `48` isn't. — molbdnilo, Aug 12 '19 at 13:48

Ted Lyngmo · Answer 1 · 2019-08-12T16:40:12.787

The two char[3000][3000]'s that you allocate on the stack is the reason for the crash.

Since there's no upper constraint on n you'd better to try to allocate it on the heap and catch the exception if it fails. This can be done by using std::vector<std::vector<char>> instead.

Replace:

int n,m;
cin >> n >> m;
char arr[3000][3000];

With something like this:

#include <vector>

size_t n, m;
std::vector<std::vector<char>> arr;

while(std::cin >> n >> m) {
    try {
        arr.resize(n, std::vector<char>(m));
        break; // success, break out of the while-loop
    } catch(const std::exception& ex) {
        // exception caught, most probably a bad_alloc
        std::cerr << ex.what() << " ... try again\n";
    }
}

As proposed in the comments, you probably don't need to store all the queries. Just deal with one query at a time.

Also, never #include <bits/stdc++.h> yourself. It's a non-standard/non-portable header file that includes a lot more than you need, and often not all you need. Instead, only include the headers you actually need.

Similarly, using namespace std; is considered bad practice.

killtheverse · Answer 2 · 2019-08-12T14:36:14.290

OK, so I think you have complicated some things here. The size of the queries is 10^6 and you are declaring the array as query[3000][3000]. Now, I don't think you need to store the queries. Consider this-

cin>>q;
while(q--)
{
    cin>>a>>i>>j;
    /*Your code here*/
}

The question states that the queries are in the form : a i j So for example if you want to perform operation 0 on first 2 strings, the query will be: 0 1 2 But you are storing the binary numbers from index 0! So, your code will perform the operation on second and third query. So, what you need to do is just take subtract 1 from values of i and j.

Why am I getting a 'Runtime Error - SIGSEGV' in my code?

2 Answers2