python/TangDou/AcWing_TiGao/T6/PaiXu/105.cpp

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

typedef long long LL;

const int N = 100010;

int row[N], col[N], s[N], c[N];

LL solve(int n, int a[]) {
    int sum = 0;
    for (int i = 1; i <= n; i++) sum += a[i];
    // 不能整除，最终无法完成平均工作
    if (sum % n) return -1;
    // 平均数
    int avg = sum / n;

    // 构建c数组
    for (int i = 1; i <= n; i++) c[i] = c[i - 1] + a[i] - avg;
    // 排序，为求中位数做准备
    sort(c + 1, c + n + 1);
    // 计算每个c[i]与中位数的差,注意下标从1开始时的写法 c[(n+1)/2]
    LL res = 0;
    for (int i = 1; i <= n; i++) res += abs(c[i] - c[(n + 1) / 2]);

    return res;
}

int n, m, T; // n行,m列，对T个摊点感兴趣
int main() {
    // 加快读入
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n >> m >> T;
    while (T--) {
        int x, y;
        cin >> x >> y;
        row[x]++, col[y]++; // x行感兴趣的摊点数+1,y列感兴趣的摊点数+1
    }

    LL r = solve(n, row), c = solve(m, col);

    if (~r && ~c)
        printf("both %lld\n", r + c);
    else if (~r)
        printf("row %lld\n", r);
    else if (~c)
        printf("column %lld\n", c);
    else
        printf("impossible\n");

    return 0;
}