Arrays and STL Containers

The goal of reading this subsection is to convince you that using C++ STL containers is beneficial to competitive programming.

Summary

Use static or size-fixed arrays, or STL vectors.

Now, I will introduce two reasons for using STL containers.

Reason 1: Containers Have Lengths Info

Once you have a container, you can use std::sort() to sort them.

Example: [CF1399A] Remove Smallest

Short Description

You are given an array of nn positive integers. Each time you can choose two integers where their absolute difference is no more than 11, and eliminate the smaller one. Answer YES if there is a way to eliminate integers until exactly one number left.

Solution

If there is a way to eliminate all but one integer, then the remaining one must be of the largest value. Thus, we can sort the array and see if for any non-largest integer can be eliminated.

#include <bits/stdc++.h>
using namespace std;
void solve() {
int n;
cin >> n;
// Declare an array of size n dynamically.
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
sort(a.begin(), a.end());
for (int i = 0; i < n - 1; i++) {
if (a[i + 1] > a[i] + 1) {
cout << "NO" << '\n';
return;
}
}
cout << "YES" << '\n';
return;
}
int main() {
int t;
cin >> t;
while (t--) solve();
return 0;
}

Reason 2: Containers Could Have Iterators

Using the iterators, your code looks more simpler and easier to understand. This is super helpful when you are using ranged for-loops.

Example: [CF1220A] Cards

Short Description

You are given a shuffled string from reading a sequence of binary digits in English. Restore the maximum possible number in binary notation.

Solution

We notice that the number of z characters represents the number of zeros, and the number of n characters represents the number of ones. Hence, our algorithm starts with counting the number of such charaters, and output all the 1's before 0's.

#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
string S;
cin >> n >> S;
int count_z = 0, count_n = 0;
// Here we use a ranged for-loop over a container.
for (char x : S) {
if (x == 'z') count_z++;
if (x == 'n') count_n++;
}
for (int i = 0; i < count_n; ++i) cout << "1 ";
for (int i = 0; i < count_z; ++i) cout << "0 ";
cout << endl;
return 0;
}

Note: on Codeforces, the autograder allows you to print a trailing space at the end of the line. This might not pass on the other online judges.

With these handy containers in C++, we are able to apply sorting to lots of challenges in a very handy way!

Edit this page