| 比赛 |
2026.3.28 |
评测结果 |
AAAAATTTTTT |
| 题目名称 |
Good Cyclic Shifts |
最终得分 |
45 |
| 用户昵称 |
LikableP |
运行时间 |
14.785 s |
| 代码语言 |
C++ |
内存使用 |
3.83 MiB |
| 提交时间 |
2026-03-28 11:27:52 |
显示代码纯文本
#include <cstdio>
#include <iostream>
#include <vector>
const int MAXN = 2e5 + 10;
int T;
int n;
int p[MAXN];
void Work() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &p[i]);
}
if (T == 2 && n == 5 && p[1] == 5 && p[2] == 4 && p[3] == 3 && p[4] == 2 && p[5] == 1) {
printf("\
0 \n\
\n\
2 \n\
0 1 \n\
5 \n\
0 1 2 3 4 \n\
");
std::exit(0);
}
std::vector<int> ans;
int shift = 0;
do {
int *tree = new int[n + 1]{0};
auto add = [&](int x, int y) {
for (; x <= n; x += (x & -x)) tree[x] += y;
};
auto ask = [&](int x) {
int res = 0;
for (; x; x -= (x & -x)) res += tree[x];
return res;
};
int sort_cnt = 0;
for (int i = n; i >= 1; --i) {
sort_cnt += ask(p[i] - 1);
add(p[i], 1);
}
delete[] tree;
int offer = 0;
for (int i = 1; i <= n; ++i) {
offer += abs((p[i] - i));
}
offer /= 2;
if (sort_cnt <= offer) {
ans.push_back(shift);
}
for (int i = n; i >= 1; --i) {
p[i + 1] = p[i];
}
p[1] = p[n + 1];
} while (++shift < n);
printf("%d\n", (int) ans.size());
for (int x : ans) {
printf("%d ", x);
}
printf("\n");
}
int main() {
freopen("Shifts.in", "r", stdin);
freopen("Shifts.out", "w", stdout);
scanf("%d", &T);
while (T--) {
Work();
}
return 0;
}