AcWing 105. 七夕祭
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <sstream>
#include <unordered_map>
#define ll long long
#define ull unsigned long long
#define re return
#define pb push_back
#define Endl "\n"
#define endl "\n"
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 100000 + 10;
const int M = 1e5 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
int T;
ll n, m, t;
ll row[N], col[N];
ll s[N], c[N];
int get(ll n, ll a[]){
for (int i = 1; i <= n; i++)
s[i] = s[i - 1] + a[i];
if(s[n] % n)
return -1;
ll avg = s[n] / n;
c[n] = 0;
for (int i = 1; i < n; i++){
c[i] = i * avg - s[i]; // 推出来的公式
}
sort(c + 1, c + 1 + n);
ll res = 0;
for (int i = 1; i <= n; i++){
res += abs(c[i] - c[(n + 1) / 2]); // 到中位数的距离
}
return res;
}
void solve(){
cin >> n >> m >> t;
for (int i = 1; i <= t; i++){
int x, y;
cin >> x >> y;
row[x]++;
col[y]++;
}
int r = get(n, row);
int c = get(m, col);
if(r != -1 && c != -1)
printf("both %lld", r + c);
else if(r != -1)
printf("row %lld", r);
else if(c != -1)
printf("column %lld", c);
else
printf("impossible");
}
int main(){
T = 1;
// cin >> T;
while(T--){
solve();
}
}