比赛 2025.12.13 评测结果 AAAAAAAAAAAAAAAAAAAA
题目名称 排列变换 最终得分 100
用户昵称 xuyuqing 运行时间 2.009 s
代码语言 C++ 内存使用 6.63 MiB
提交时间 2025-12-13 09:53:38
显示代码纯文本

#include <cstdio>
#include <iostream>

using namespace std;

const int N = 1000010;

int n;
int nums[N];
int magic[2 * N];
int id;
int maxn = -1;

int main () {

	freopen ("permutrans.in", "r", stdin);
	freopen ("permutrans.out", "w", stdout);

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

	for (int i = 1; i <= n; i++) {
		int numSame = (nums[i] - i + n) % n;
		int numFirst = (1 - i + n) % n;
		// cout << numFirst << ' ' << numSame << endl;
		if (numFirst > numSame) {
			numSame += n;
		}
		magic[numFirst]++;
		magic[numSame + 1]--;
	}

	for (int i = 1; i < 2 * n; i++) {
		magic[i] += magic[i - 1];
	}
	for (int i = 0; i < n; i++) {
		magic[i] += magic[i + n];
		if (magic[i] > maxn) {
			maxn = magic[i];
			id = i;
		}
	}
	cout << maxn << ' ' << id << endl;
	
	return 0;
}