QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#589622#5305. Oscar is All You Needlouhao088WA 1ms3856kbC++232.0kb2024-09-25 19:06:392024-09-25 19:06:40

Judging History

你现在查看的是最新测评结果

  • [2024-09-25 19:06:40]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3856kb
  • [2024-09-25 19:06:39]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

const int N = 1050;
int n, p[N], tmp[N], id[N];
vector <pair<int, int> > s;
int flag;

void work(int x, int y) {
    s.push_back(make_pair(x, y));
    tmp[0] = 0;
    for (int i = n - y + 1; i <= n; i++) tmp[++tmp[0]] = p[i];
    for (int i = x + 1; i <= n - y; i++) tmp[++tmp[0]] = p[i];
    for (int i = 1; i <= x; i++) tmp[++tmp[0]] = p[i];
    for (int i = 1; i <= n; i++) p[i] = tmp[i], id[p[i]] = i;
    // printf("%d %d\n", x, y);
    // for (int i = 1; i <= n; i++) printf("%d ", p[i]); printf("\n");
}

void write() {
    bool mor = 0;
    if (n != 3 && p[n] != n) mor = 1;
    printf("%d\n", s.size() + mor);
    for (int i = 0; i < s.size(); i++) {
        printf("%d %d\n", s[i].first, s[i].second);
        if (mor && i == flag) printf("1 1\n");
    }
}

void slove() {
    s.clear();
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &p[i]), id[p[i]] = i;

    if (n == 3) {
        if (p[1] > p[3]) work(1, 1);
        write(); return ;
    }

    flag = 0;
    if (id[n] == id[n - 1] + 1 || id[n - 1] == id[n] + 1) {
        int l = min(id[n], id[n - 1]), r = max(id[n], id[n - 1]);
        if (r != n) work(l, 1);
            else work(1, 1);
        flag = 1;
    }
    work(min(id[n], id[n - 1]), n - max(id[n], id[n - 1]) + 1);

    if (p[1] != 1) {
        work(id[1] - 1, n - id[1]);
        work(id[1] - 2, n - id[1] + 1);
    }
    for (int i = 2; i <= n - 2; i++) {
        if (p[i] == i) continue;
        if (id[i] == n) {
            work(i - 1, 2);
            work(1, i - 1);
        }
        else {
            work(i - 1, 1);
            work(id[i] - 1, i - 1);
        }
    }

    // for (int i = 1; i <= n - 2; i++)
        // assert(p[i] == i);
    //  for (int i = 1; i <= n; i++) printf("%d ", p[i]);
    //  printf("\n");

    write();
}

int main() {
    int t; scanf("%d", &t);
    while (t--) slove();
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3856kb

input:

2
3
1 3 2
5
4 1 2 3 5

output:

0
6
1 1
1 1
1 3
2 2
1 1
3 1

result:

ok OK in maximum 6 operations

Test #2:

score: -100
Wrong Answer
time: 1ms
memory: 3828kb

input:

120
3
1 3 2
3
3 2 1
3
2 3 1
5
1 2 3 4 5
12
11 9 2 8 3 10 6 1 4 7 5 12
36
24 9 7 3 31 15 13 1 4 33 11 29 16 23 2 25 35 21 32 14 6 18 17 26 28 8 27 22 20 36 10 19 34 12 30 5
4
4 2 3 1
5
3 5 2 1 4
4
1 2 4 3
10
5 7 4 9 6 8 1 3 10 2
5
3 1 5 2 4
5
3 5 1 2 4
3
3 1 2
13
3 1 2 11 12 13 8 6 5 4 10 9 7
16
12 8...

output:

0
1
1 1
1
1 1
6
1 1
1 2
1 3
2 2
1 1
3 1
19
1 1
7 4
3 8
1 1
3 1
2 1
2 2
3 1
4 3
4 1
2 4
5 1
5 5
6 1
2 6
7 1
3 7
8 2
1 8
69
17 7
26 9
8 27
1 1
34 1
2 1
24 2
3 1
5 3
4 1
13 4
5 1
4 5
6 1
11 6
7 1
24 7
8 1
5 8
9 1
12 9
10 1
21 10
11 1
8 11
12 1
15 12
13 1
13 13
14 1
10 14
15 1
4 15
16 1
10 16
17 2
1 17
...

result:

wrong answer Integer parameter [name=x] equals to 0, violates the range [1, 5]