52 lines
1.3 KiB
C++
52 lines
1.3 KiB
C++
#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;
|
||
} |