QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#188648#5508. Job for a HobbitAPJifengcAC ✓15ms5320kbC++144.6kb2023-09-26 09:13:442023-09-26 09:13:44

Judging History

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

  • [2023-09-26 09:13:44]
  • 评测
  • 测评结果：AC
  • 用时：15ms
  • 内存：5320kb
查看
  • [2023-09-26 09:13:44]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 55;
int T;
int n, k;
int a[MAXN][MAXN];
int top[MAXN];
int b[MAXN][MAXN];
int main() {
    scanf("%d", &T);
    while (T--) {
        int sum = 0;
        map<int, int> cnt;
        scanf("%d%d", &n, &k);
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= k; j++) scanf("%d", &a[i][j]), cnt[a[i][j]]++;
        }
        top[0] = top[n + 1] = 0;
        for (int i = 1; i <= n; i++) top[i] = k;
        for (auto p : cnt) sum += (p.second + k - 1) / k;
        if (sum > n + 2) { printf("NIE\n"); continue; }
        int x = 1, y = 1;
        for (auto p : cnt) {
            while (p.second--) {
                b[x][y] = p.first;
                y++;
                if (y == k + 1) y = 1, x++;
            }
        }
        if (k == 1) {
            printf("TAK\n0\n");
            continue;
        }
        vector<pair<int, int>> ans;
        getchar();
        auto opt = [&](int i, int j) {
            assert(abs(i - j) == 1);
            assert(top[i]);
            assert(top[j] < k);
            a[j][++top[j]] = a[i][top[i]--];
            ans.push_back({ i, j });
            // printf("\n");
            // for (int j = k; j >= 1; j--) {
            //     for (int i = 0; i <= n + 1; i++) {
            //         if (top[i] >= j) printf("% 3d ", a[i][j]);
            //         else printf("    ");
            //     }
            //     printf("\n");
            // }
            // getchar();
        };
        for (int i = n; i >= 1; i--) {
            for (int j = 1; j <= k; j++) opt(i, i + 1);
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= k; j++) {
                int v = b[i][j];
                int x = 0, y = 0;
                for (int p = i + 1; p <= n + 1; p++) {
                    for (int q = 1; q <= top[p]; q++) {
                        if (a[p][q] == v) {
                            x = p, y = q;
                            goto nxt;
                        }
                    }
                }
                nxt:;
                for (int p = i + 1; p < x; p++) {
                    while (top[p]) opt(p, p - 1);
                }
                for (int p = x; p > i + 1; p--) {
                    if (y == 1 && top[p] == k) {
                        int w;
                        for (w = p - 2; w >= 0; w--) {
                            if (top[w] != k) break;
                        }
                        for (int q = w + 1; q <= p - 2; q++) opt(q, q - 1);
                        opt(p, p - 1), opt(p - 1, p - 2);
                        while (top[p]) opt(p, p - 1);
                        while (top[p - 2]) opt(p - 2, p - 1), opt(p - 1, p);
                        for (int q = p - 3; q >= w; q--) opt(q, q + 1);
                        while (top[p - 2]) opt(p - 2, p - 1);
                        y = k - 1;
                    } else {
                        while (top[p] != y - 1) opt(p, p - 1);
                        y = top[p - 1];
                        while (top[p - 2]) {
                            opt(p - 2, p - 1);
                            if (top[p] != k) opt(p - 1, p);
                        }
                    }
                }
                while (top[i + 1] != y) opt(i + 1, i);
                opt(i + 1, i), opt(i, i - 1);
                while (top[i]) opt(i, i + 1);
            }
            for (int p = n; p >= i; p--) {
                while (top[p] && top[p + 1] != k) {
                    int x = p;
                    while (x != n + 1 && top[x + 1] != k) {
                        opt(x, x + 1);
                        x++;
                    }
                }
            }
        }
        for (int i = n - 1; i >= 0; i--) {
            while (top[i]) {
                int x = i;
                while (x != n + 1 && top[x + 1] != k && (!top[x + 1] || a[x + 1][1] == a[x][top[x]])) {
                    opt(x, x + 1);
                    x++;
                }
                if (x == i) break;
            }
        }
        printf("TAK\n");
        printf("%lu\n", ans.size());
        for (auto p : ans) {
            printf("%d %d\n", p.first, p.second);
        }
    }
    return 0;
}
/*
2
2 2
1 2
2 1


1
3 4
2 2 2 2
2 2 2 2
2 2 2 1


1

10 7
11 5 6 5 2 1 2
8 7 1 9 10 6 4
6 8 4 6 2 12 9
12 3 10 5 11 4 7
9 11 4 2 9 3 9
6 7 5 11 1 10 6
11 7 6 7 12 1 1
5 3 2 3 4 7 12
3 8 11 9 12 9 8
1 12 12 4 10 1 2

10 2
1 3
3 4
5 2
6 7
8 1
3 9
4 5
6 7
8 2
1 9


*/
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3692kb

input:

2
2 2
1 2
2 1
1 4
1 2 3 4

output:

TAK
30
2 3
2 3
1 2
1 2
2 1
1 0
2 1
3 2
2 1
3 2
1 2
2 3
1 2
2 3
2 1
1 0
3 2
3 2
2 1
2 3
3 2
2 1
1 2
2 3
1 2
2 3
0 1
1 2
0 1
1 2
NIE

result:

ok Correct! Used 30 swaps

Test #2:

score: 0
Accepted
time: 1ms
memory: 3780kb

input:

25
2 7
4 1 2 2 3 2 4
4 4 6 4 2 2 5
2 5
6 5 5 3 3
1 6 5 2 5
2 8
1 4 2 1 4 1 2 1
1 3 4 4 2 2 1 2
2 4
1 1 5 2
1 5 2 2
2 10
3 5 4 5 5 2 1 3 5 2
5 2 2 1 5 1 3 3 4 2
2 8
2 4 3 3 4 2 1 2
5 1 4 1 2 6 3 4
2 9
4 3 4 3 4 2 4 1 2
2 4 4 2 2 3 3 3 4
2 4
4 1 3 1
4 2 4 3
2 4
5 1 2 2
2 4 3 2
2 7
1 2 4 5 2 5 2
4 5 5 ...

output:

NIE
NIE
TAK
169
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
1 0
1 2
1 2
1 2
1 2
1 2
1 2
1 2
2 1
2 1
2 1
2 1
2 1
2 1
1 0
1 2
1 2
1 2
1 2
1 2
2 1
2 1
2 1
2 1
1 0
1 2
1 2
1 2
2 1
1 0
2 1
2 1
2 1
2 1
3 2
3 2
3 2
3 2
3 2
3 2
3 2
1 2
2 3
1 2
2 3
1 2
2 3
...

result:

ok Correct! Used 1487 swaps

Test #3:

score: 0
Accepted
time: 7ms
memory: 4300kb

input:

1
50 10
2 2 2 2 2 1 2 1 1 2
2 1 2 1 1 2 2 2 2 2
2 1 1 2 2 2 2 1 1 1
2 2 1 2 2 2 1 1 1 2
2 1 1 2 1 2 2 1 2 1
2 1 2 1 1 1 2 1 2 2
1 2 1 1 2 2 1 1 2 1
2 2 1 1 2 2 2 1 1 2
1 2 2 2 2 1 1 2 1 1
2 2 2 1 2 1 1 2 1 1
2 2 1 2 2 1 1 1 1 1
1 2 2 1 2 2 2 1 1 1
2 2 2 1 2 2 1 1 2 2
1 2 1 2 1 1 1 1 2 2
1 2 1 1 2 2 ...

output:

TAK
85719
50 51
50 51
50 51
50 51
50 51
50 51
50 51
50 51
50 51
50 51
49 50
49 50
49 50
49 50
49 50
49 50
49 50
49 50
49 50
49 50
48 49
48 49
48 49
48 49
48 49
48 49
48 49
48 49
48 49
48 49
47 48
47 48
47 48
47 48
47 48
47 48
47 48
47 48
47 48
47 48
46 47
46 47
46 47
46 47
46 47
46 47
46 47
46 47
46...

result:

ok Correct! Used 85719 swaps

Test #4:

score: 0
Accepted
time: 15ms
memory: 5320kb

input:

1
50 10
33 28 16 37 35 47 28 35 31 21
47 40 33 25 16 40 50 25 13 33
10 14 48 38 1 38 32 43 28 18
11 16 1 51 4 45 16 31 27 41
52 18 32 51 17 31 38 48 49 47
5 24 20 48 51 20 29 32 35 20
39 18 21 45 10 30 11 5 32 32
5 46 19 39 30 26 15 17 15 8
15 15 21 25 41 28 6 8 6 20
47 28 34 12 44 16 48 49 52 47
23...

output:

TAK
187995
50 51
50 51
50 51
50 51
50 51
50 51
50 51
50 51
50 51
50 51
49 50
49 50
49 50
49 50
49 50
49 50
49 50
49 50
49 50
49 50
48 49
48 49
48 49
48 49
48 49
48 49
48 49
48 49
48 49
48 49
47 48
47 48
47 48
47 48
47 48
47 48
47 48
47 48
47 48
47 48
46 47
46 47
46 47
46 47
46 47
46 47
46 47
46 47
4...

result:

ok Correct! Used 187995 swaps

Test #5:

score: 0
Accepted
time: 1ms
memory: 3744kb

input:

5
10 1
11
2
10
3
1
12
8
4
5
7
10 7
11 5 6 5 2 1 2
8 7 1 9 10 6 4
6 8 4 6 2 12 9
12 3 10 5 11 4 7
9 11 4 2 9 3 9
6 7 5 11 1 10 6
11 7 6 7 12 1 1
5 3 2 3 4 7 12
3 8 11 9 12 9 8
1 12 12 4 10 1 2
10 7
9 8 12 8 10 7 4
1 1 10 7 3 5 1
11 6 11 5 2 4 12
6 12 8 3 8 6 8
12 7 4 1 11 8 6
7 6 2 5 9 3 6
12 10 4 9 ...

output:

TAK
0
TAK
3437
10 11
10 11
10 11
10 11
10 11
10 11
10 11
9 10
9 10
9 10
9 10
9 10
9 10
9 10
8 9
8 9
8 9
8 9
8 9
8 9
8 9
7 8
7 8
7 8
7 8
7 8
7 8
7 8
6 7
6 7
6 7
6 7
6 7
6 7
6 7
5 6
5 6
5 6
5 6
5 6
5 6
5 6
4 5
4 5
4 5
4 5
4 5
4 5
4 5
3 4
3 4
3 4
3 4
3 4
3 4
3 4
2 3
2 3
2 3
2 3
2 3
2 3
2 3
1 2
1 2
1 2
...

result:

ok Correct! Used 8097 swaps

Test #6:

score: 0
Accepted
time: 3ms
memory: 3928kb

input:

2
25 10
27 26 27 26 27 26 27 26 27 26
26 27 26 27 26 27 26 27 26 27
25 25 25 25 25 25 25 25 25 25
24 24 24 24 24 24 24 24 24 24
23 23 23 23 23 23 23 23 23 23
22 22 22 22 22 22 22 22 22 22
21 21 21 21 21 21 21 21 21 21
20 20 20 20 20 20 20 20 20 19
19 19 19 19 19 19 19 19 18 18
18 18 18 18 18 18 18 1...

output:

TAK
64880
25 26
25 26
25 26
25 26
25 26
25 26
25 26
25 26
25 26
25 26
24 25
24 25
24 25
24 25
24 25
24 25
24 25
24 25
24 25
24 25
23 24
23 24
23 24
23 24
23 24
23 24
23 24
23 24
23 24
23 24
22 23
22 23
22 23
22 23
22 23
22 23
22 23
22 23
22 23
22 23
21 22
21 22
21 22
21 22
21 22
21 22
21 22
21 22
21...

result:

ok Correct! Used 68214 swaps

Test #7:

score: 0
Accepted
time: 14ms
memory: 5304kb

input:

1
50 10
1 1 1 37 35 47 1 35 31 21
47 40 1 25 1 40 1 25 13 1
10 14 48 38 1 38 32 43 1 18
11 1 1 1 4 45 1 31 27 41
1 18 32 1 17 31 38 48 49 47
1 24 1 48 1 1 29 32 35 1
39 18 21 45 10 30 11 1 32 32
1 46 19 39 30 26 15 17 15 8
15 15 21 25 41 1 6 8 6 1
47 1 34 12 1 1 48 49 1 47
23 18 1 1 37 1 41 1 2 30
4...

output:

TAK
172441
50 51
50 51
50 51
50 51
50 51
50 51
50 51
50 51
50 51
50 51
49 50
49 50
49 50
49 50
49 50
49 50
49 50
49 50
49 50
49 50
48 49
48 49
48 49
48 49
48 49
48 49
48 49
48 49
48 49
48 49
47 48
47 48
47 48
47 48
47 48
47 48
47 48
47 48
47 48
47 48
46 47
46 47
46 47
46 47
46 47
46 47
46 47
46 47
4...

result:

ok Correct! Used 172441 swaps

Test #8:

score: 0
Accepted
time: 1ms
memory: 3640kb

input:

1
50 10
15 52 42 32 47 29 31 51 12 48
43 19 14 2 28 39 51 10 43 36
33 6 29 11 4 18 12 41 15 34
24 2 48 30 25 23 34 17 9 28
24 8 17 4 21 14 42 19 48 30
23 16 30 9 33 25 33 36 21 12
36 18 46 35 31 13 44 34 15 50
34 11 33 38 9 23 9 42 4 3
37 12 2 41 7 34 23 16 10 27
24 8 38 16 24 11 47 29 3 50
34 52 47...

output:

NIE

result:

ok Correct! Used 0 swaps
English 繁體中文 简体中文

Server Time: 2024-12-02 09:42:41 | OpenSource Project