Language: C++

//
//  main.cpp
//  Algorithms and Data Structures
//
//  Created by kawauso.
//

#include <iostream>
#include <string>
#include <vector>
#include <cassert>
#include <tuple>

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REPEAT(i, n) FOR(i, 0, n)
#define DECFOR(i, a, b) for (int i = (a); (b) < i; --i)

using namespace std;

bool isStable(std::vector<std::tuple<char, int>> in, std::vector<std::tuple<char, int>> out);
int insertionSort(std::vector<int> &a, int n, int g);

void c_3_6() {
	int n;
	int cnt;

	// input
	std::cin >> n;
	vector<int> a(n);
	REPEAT(i, n) {
		std::cin >> a[i];
	}

#if 0
	std::vector<int> const g = {4, 1};
#else
	std::vector<int> g;
#if 0
	for (int i = 1; i < n; i++) {
		g.push_back(i);
	}
#elsif 0
	// prime numbers
	g.push_back(1);
	for (int i = 2; i < n; i++) {
		bool p;

		p = true;
		for (int j = 1; j < g.size(); j++) {
			if (i % g[j] == 0) {
				p = false;
				break;
			}
		}
		if (p) {
			g.push_back(i);
		}
	}
	std::reverse(g.begin(), g.end());
#else
	for (int i = 1; i < n; i = i * 3 + 1) {
		g.push_back(i);
	}
	std::reverse(g.begin(), g.end());
#endif
#endif
	cnt = 0;
	for (int i = 0; i < g.size(); i++) {
		cnt += insertionSort(a, n, g[i]);
	}

	// output
	std::cout << g.size() << std::endl;
	REPEAT(i, g.size()) {
		std::cout << (i == 0 ? "" : " ") << g[i];
	}
	std::cout << std::endl;
	std::cout << cnt << std::endl;
	REPEAT(i, a.size()) {
		std::cout << a[i] << std::endl;
	}
	// 正解との違い: 効果的なgの数列は g(n)=3*g(n-1)+1 だそうな
}

int insertionSort(std::vector<int> &a, int n, int g) {
	int cnt;

	cnt = 0;
	FOR(i, g, n) {
		int j;

		const auto v = a[i];
		j = i - g;
		while (j >= 0 and a[j] > v) {
			a[j + g] = a[j];
			j -= g;
			cnt++;
		}
		a[j + g] = v;
	}
	return cnt;
}

void c_3_5() {
	int n;
	int minj;

	// input
	std::cin >> n;
	std::vector<std::tuple<char, int>> a(n);
	std::vector<std::tuple<char, int>> b(n);
	std::vector<std::tuple<char, int>> c(n);
	REPEAT(i, n) {
		std::string v;
		char v1;
		int v2;

		std::cin >> v;
		const int count = std::sscanf(v.c_str(), "%c%d", &v1, &v2);
		assert(count == 2);
		a[i] = std::make_tuple(v1, v2);
		c[i] = b[i] = a[i];
	}

	// buble sort
	REPEAT(i, n) {
		for (int j = n - 1; j > i; j--) {
			if (std::get<1>(a[j]) >= std::get<1>(a[j - 1])) {
				continue;
			}
			swap(a[j], a[j - 1]);
		}
	}
	// output
	REPEAT(i, a.size()) {
		std::cout << (i == 0 ? "" : " ") << std::get<0>(a[i]) << std::get<1>(a[i]);
	}
	std::cout << std::endl;
	std::cout << (isStable(c, a) ? "Stable" : "Not stable") << std::endl;

	// selection sort
	FOR(i, 0, n) {
		minj = i;
		FOR(j, i + 1, n) {
			if (std::get<1>(b[j]) >= std::get<1>(b[minj])) {
				continue;
			}
			minj = j;
		}
		if (minj == i) {
			continue;
		}
		std::swap(b[i], b[minj]);
	}
	// output
	REPEAT(i, b.size()) {
		std::cout << (i == 0 ? "" : " ") << std::get<0>(b[i]) << std::get<1>(b[i]);
	}
	std::cout << std::endl;
	std::cout << (isStable(c, b) ? "Stable" : "Not stable") << std::endl;
	// 正解との違い: 入力はsscanfを使わなくても cin >> suit >> value でできた
	// 安定的かどうかをバブルソートを元に選択ソートを判定してた、ずるい
	// 正解は相変わらず同じものを比較しているし、同じものを交換している
}

bool isStable(std::vector<std::tuple<char, int>> const in, std::vector<std::tuple<char, int>> const out) {
	// combination round-trip
	REPEAT(i, in.size()) {
		FOR(j, i + 1, in.size()) {
			REPEAT(k, out.size()) {
				FOR(l, k + 1, out.size()) {
					if (std::get<1>(in[i]) == std::get<1>(in[j]) && in[i] == out[l] && in[j] == out[k]) {
						// found reverse ordered combinations
						return false;
					}
				}
			}
		}
	}
	return true;
}

void c_3_4() {
	int n;
	int minj;
	int count;

	cin >> n;
	vector<int> a(n);
	REPEAT(i, n) {
		cin >> a[i];
	}

	count = 0;
	FOR(i, 0, n) {
		minj = i;
		FOR(j, i + 1, n) {
			if (a[j] >= a[minj]) {
				continue;
			}
			minj = j;
		}
		if (minj == i) {
			continue;
		}
		swap(a[i], a[minj]);
		++count;
	}

	REPEAT(k, a.size()) {
		cout << (k ? " " : "") << a[k];
	}
	cout << endl;
	cout << count << endl;
	// 正解との違い: 正解はswapしなくてもいい時もswapしている。比較も初回同じものを比較している。
	// こっちの方がより無駄がない。
}

void c_3_3() {
	int n;
	bool flag;
	int count;

	cin >> n;
	// int price[n];
	vector<int> a(n);
	REPEAT(i, n) {
		cin >> a[i];
	}

	flag = true;
	count = 0;
	for (int i = 0; flag; i++) {
		flag = false;
		DECFOR(j, n - 1, i) {
			if (a[j] >= a[j - 1]) {
				continue;
			}
			const auto v = a[j];
			a[j] = a[j - 1];
			a[j - 1] = v;
			flag = true;
			++count;
		}
	}
	REPEAT(k, a.size()) {
		cout << (k ? " " : "") << a[k];
	}
	cout << endl;
	cout << count << endl;
	// 初解と正解との違い: 交換と非交換を繰り返して出会った一番小さい要素を移動させているという理解が欠如していた
	// よって動作的には正しいが無駄な部分を走査していた
	// swap関数があるのを知らなかった
}

void c_3_2() {
	int n;

	cin >> n;
	// int price[n];
	vector<int> a(n);
	REPEAT(i, n) {
		cin >> a[i];
	}
	REPEAT(k, a.size()) {
		cout << (k ? " " : "") << a[k];
	}
	cout << endl;
	FOR(i, 1, n) {
		int j;

		const auto v = a[i];
		j = i - 1;
		while (j >= 0 and a[j] > v) {
			a[j + 1] = a[j];
			j--;
		}
		a[j + 1] = v;
		REPEAT(k, a.size()) {
			cout << (k ? " " : "") << a[k];
		}
		cout << endl;
	}
	//正解との違い: 特になし
}

void c_2_5() {
	//string s;
	int n;
	cin >> n;
	// int price[n];
	vector<int> price(n);
	REPEAT(i, n) {
		cin >> price[i];
	}
	int maxPrice[n];
	int currentMaxPrice;
	currentMaxPrice = 0;    // or -infinite
	for (int i = n - 1; i >= 0; i--) {
		if (price[i] > currentMaxPrice) {
			currentMaxPrice = price[i];
		}
		maxPrice[i] = currentMaxPrice;
	}
	int maxUp = maxPrice[1] - price[0];
	for (int i = 1; i < n - 1; i++) {
		const int diff = maxPrice[i + 1] - price[i];
		if (diff > maxUp) {
			maxUp = diff;
		}
	}
	cout << maxUp << "\n";
	// 正解との違い: 最大ではなく最小を保持するようにすれば先頭から処理でき、配列を使う必要すらない
	// 競技プログラミングとしてのアドバイス: FOR, REPEATマクロを使いタイプミスをする可能性を減らす
	//   配列の変わりにvectorを用いて宣言以上の領域へのアクセスを検知したりsegmentation faultで落ちるようにする
}

int main(int argc, const char * argv[]) {
	ios::sync_with_stdio(false);
	c_3_6();
	return 0;
}



Compiler output:
a.cc: In function 'void c_3_6()':
a.cc:64:14: error: 'reverse' is not a member of 'std'
   64 |         std::reverse(g.begin(), g.end());
      |              ^~~~~~~