编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#28887 #2065. 数字华容道 Accepted 100 1275 ms 14200 K C++ 17 (Clang) / 2.2 K banned22 2025-03-15 17:04:00
显示原始代码
#include <iostream>
#include <vector>
using namespace std;

// 归并排序并计算逆序数
int mergeAndCount(vector<int>& nums, int left, int mid, int right) {
    vector<int> temp(right - left + 1);
    int i = left, j = mid + 1, k = 0;
    int inversion = 0;

    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j]) {
            temp[k++] = nums[i++];
        } else {
            temp[k++] = nums[j++];
            inversion += (mid - i + 1);  // 统计逆序数
        }
    }

    while (i <= mid) temp[k++] = nums[i++];
    while (j <= right) temp[k++] = nums[j++];

    for (int p = 0; p < k; p++) {
        nums[left + p] = temp[p];
    }

    return inversion;
}

int countInversions(vector<int>& nums, int left, int right) {
    int inversion = 0;
    if (left < right) {
        int mid = left + (right - left) / 2;
        inversion += countInversions(nums, left, mid);
        inversion += countInversions(nums, mid + 1, right);
        inversion += mergeAndCount(nums, left, mid, right);
    }
    return inversion;
}

int main() {
    int m, n;
    cin >> m >> n;
    vector<vector<int>> grid(m, vector<int>(n));
    int zero_row = -1;

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> grid[i][j];
            if (grid[i][j] == 0) {
                zero_row = i;
            }
        }
    }

    // 展开为一维数组并去除0
    vector<int> nums;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] != 0) {
                nums.push_back(grid[i][j]);
            }
        }
    }

    // 计算逆序数
    int inversion = countInversions(nums, 0, nums.size() - 1);

    // 计算空格所在行从下数的行号
    int row_from_bottom = m - zero_row;

    // 判断条件
    if (n % 2 == 1) {
        // 奇数列,仅看逆序数是否为偶数
        cout << (inversion % 2 == 0 ? "YES" : "NO") << endl;
    } else {
        // 偶数列,逆序数+空格行数的奇偶性是否为奇数
        int total = inversion + row_from_bottom;
        cout << (total % 2 == 1 ? "YES" : "NO") << endl;
    }

    return 0;
}
子任务 #1
Accepted
得分:100
测试点 #1
Accepted
得分:100
用时:3 ms
内存:324 KiB

输入文件(test1.in

3 3
1 2 6 
7 3 8 
0 4 5 

答案文件(test1.out

YES

用户输出

YES

系统信息

Exited with return code 0
测试点 #2
Accepted
得分:100
用时:3 ms
内存:344 KiB

输入文件(test2.in

3 3
7 1 5 
6 0 2 
3 4 8 

答案文件(test2.out

YES

用户输出

YES

系统信息

Exited with return code 0
测试点 #3
Accepted
得分:100
用时:4 ms
内存:328 KiB

输入文件(test3.in

4 4
13 11 1 9 
15 2 14 7 
0 10 3 8 
4 5 6 12 

答案文件(test3.out

YES

用户输出

YES

系统信息

Exited with return code 0
测试点 #4
Accepted
得分:100
用时:3 ms
内存:284 KiB

输入文件(test4.in

4 4
14 3 9 8 
4 15 5 0 
1 2 6 7 
10 11 12 13 

答案文件(test4.out

NO

用户输出

NO

系统信息

Exited with return code 0
测试点 #5
Accepted
得分:100
用时:4 ms
内存:412 KiB

输入文件(test5.in

4 4
9 13 2 5 
1 14 12 0 
3 4 10 7 
8 6 11 15 

答案文件(test5.out

NO

用户输出

NO

系统信息

Exited with return code 0
测试点 #6
Accepted
得分:100
用时:7 ms
内存:468 KiB

输入文件(test6.in

100 100
7690 5682 2677 2004 5559 6119 4307 2035 8893 7862 9155 2640 4139 6211 1754 6042 8035 8694 1
<48999 bytes omitted>

答案文件(test6.out

YES

用户输出

YES

系统信息

Exited with return code 0
测试点 #7
Accepted
得分:100
用时:7 ms
内存:456 KiB

输入文件(test7.in

100 100
7131 5702 6393 2569 6232 2219 5826 1730 3120 8643 4870 8412 4828 9339 2366 738 5908 5688 52
<48999 bytes omitted>

答案文件(test7.out

NO

用户输出

NO

系统信息

Exited with return code 0
测试点 #8
Accepted
得分:100
用时:477 ms
内存:14068 KiB

输入文件(test8.in

1000 1000
852093 582459 126709 111945 392720 997041 498864 532066 280215 433547 734819 780448 18612
<6890801 bytes omitted>

答案文件(test8.out

YES

用户输出

YES

系统信息

Exited with return code 0
测试点 #9
Accepted
得分:100
用时:508 ms
内存:14200 KiB

输入文件(test9.in

1000 1000
425610 18558 726158 634073 689595 11109 521599 44245 742153 819901 371590 568407 886681 3
<6890801 bytes omitted>

答案文件(test9.out

YES

用户输出

YES

系统信息

Exited with return code 0
测试点 #10
Accepted
得分:100
用时:259 ms
内存:7920 KiB

输入文件(test10.in

587 931
402769 239103 45894 99675 444353 214471 33158 331145 254043 429952 47540 544790 544051 3134
<3715452 bytes omitted>

答案文件(test10.out

YES

用户输出

YES

系统信息

Exited with return code 0