AIOJ

Arrays are containers that store objects of the same type. The objects stored in an array do not have names; they are accessed through their positions. The size of an array is fixed, so its length cannot be changed arbitrarily.

Defining Arrays

An array declaration has the form a[d], where a is the array's name and d is the number of elements in the array. At compile time, d must be known; in other words, d must be an integer constant expression.

unsigned int d1 = 42;
const int d2 = 42;
int arr1[d1];  // Error: d1 is not a constant expression
int arr2[d2];  // Correct: arr2 is an array of length 42

An array cannot be assigned directly to another array:

int arr1[3];
int arr2 = arr1;  // Error
arr2 = arr1;      // Error

Large arrays should generally be defined as global variables. Local variables are created in the stack area, so an excessively large array (larger than the stack size) causes a stack overflow and consequently an RE. If an array is declared in global scope, it is created in the static area.

Accessing Array Elements

Elements in an array can be accessed with the subscript operator []. Array indices (the values inside the square brackets) start at 0. For an array containing 10 elements, the indices are 0 through 9, not 1 through 10. In OI, however, for convenience we often allocate one extra position and leave the first element unused, accessing elements starting from index 1.

Example 1: Read an integer $n$ from standard input, then read $n$ numbers into an array, where $n\leq 1000$ .

#include <iostream>
using namespace std;

int arr[1001];  // The index range of arr is [0, 1001)

int main() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> arr[i];
  }
}

Example 2: (continuing Example 1) Find the sum of the elements in array arr and output it. The sum of all elements in the array is at most $2^{31} - 1$ .

#include <iostream>
using namespace std;

int arr[1001];

int main() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> arr[i];
  }

  int sum = 0;
  for (int i = 1; i <= n; ++i) {
    sum += arr[i];
  }

  printf("%d\n", sum);
  return 0;
}

Out-of-Bounds Index Access

An array index $\mathit{idx}$ must satisfy $0\leq \mathit{idx}< \mathit{size}$ . If the index is outside this range, the behavior is undefined and may produce unpredictable consequences, such as a segmentation fault or modifying a variable other than the intended one.

Multidimensional Arrays

A multidimensional array is essentially an “array of arrays”: the elements of the outer array are themselves arrays. A two-dimensional array requires two dimensions to define it: the length of the array and the length of the arrays inside it. Accessing a two-dimensional array requires writing two indices:

int arr[3][4];  // An array of length 3 whose elements are arrays of 4 ints
                // (that is, arrays of length 4 whose elements are ints)
arr[2][1] = 1;  // Access the two-dimensional array

We often use nested for loops to process two-dimensional arrays.

Example: Read two numbers $n$ and $m$ from standard input, representing the height and width of a black-and-white image, where $n,m\leq 1000$ . Each of the next $n$ lines contains $m$ space-separated numbers representing the brightness at that position. Read the image and store it in a two-dimensional array.

const int MAXN = 1001;
int pic[MAXN][MAXN];
int n, m;

cin >> n >> m;
for (int i = 1; i <= n; ++i)
  for (int j = 1; j <= m; ++j) cin >> pic[i][j];

Similarly, you can define three-dimensional, four-dimensional, and even higher-dimensional arrays.