AcWing 105. 七夕祭
原题链接
困难
作者:
Aleia
,
2024-10-10 16:01:39
,
所有人可见
,
阅读 1
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int row[N],col[N];
int pre[N];
long long handle(int arr[],int n)
{
long long ans=0;
for(int i=1;i<=n;i++) pre[i] = pre[i-1] + (arr[i] - arr[0]/n);
sort(pre+1,pre+n+1);
for(int i=1;i<=n;i++) ans += abs(pre[i] - pre[(n+1)/2]);
return ans;
}
int main()
{
int n,m,t;
cin>>n>>m>>t;
while(t--)
{
int x,y;
cin>>x>>y;
row[x]++,col[y]++;
}
for(int i=1;i<=n;i++) row[0] += row[i];
for(int i=1;i<=m;i++) col[0] += col[i];
if(row[0]%n==0 && col[0]%m==0) cout<<"both"<<" "<<handle(row,n)+handle(col,m);
else if(row[0]%n==0) cout<<"row"<<" "<<handle(row,n);
else if(col[0]%m==0) cout<<"column"<<" "<<handle(col,m);
else cout<<"impossible";
return 0;
}