044.md

044 - Shift and Swapping (★3)

解答

T == 2 のとき、実際に要素を動かしてしまうと時間がかかります。オフセット値（移動量）だけを記録し、T == 1, T == 3 での操作に使うインデックス値を、オフセット値に応じてシフトします。

#include <iostream>
#include <vector>
#include <utility> // std::swap()

// オフセット値をもとに, 対応するインデックス値に変換
int OffsetIndex(int i, int offset, int N)
{
	// 例: i = 1, offset = 2, N = 4 のとき
	// (1 - 2 + 4) % N = 3
	return (i - offset + N) % N;
}

int main()
{
	// 長さ N の整数列, Q 個のクエリ
	int N, Q;
	std::cin >> N >> Q;

	std::vector<int> A(N);
	for (auto& a : A)
	{
		std::cin >> a;
	}

	// オフセット値
	int offset = 0;

	for (int i = 0; i < Q; ++i)
	{
		int T, x, y;
		std::cin >> T >> x >> y;

		if (T == 1)
		{
			// 要素を交換
			std::swap(A[OffsetIndex(x - 1, offset, N)], A[OffsetIndex(y - 1, offset, N)]);
		}
		else if (T == 2)
		{
			// オフセット値をインクリメント, オフセット値が N 以上にならないよう %= N
			++offset %= N;
		}
		else
		{
			// 要素を出力
			std::cout << A[OffsetIndex(x - 1, offset, N)] << '\n';
		}
	}
}