cf1004d Sonya and Matrix

OI 思维
文章目录

首先如果有答案的话,那我们一定能旋转到

1
2
3
4
5
6
7
-------
|\ | |
|0\| |
|-----|
| | |
| | |
-------

这样的位置。

那么我们设离左上角的距离 $a=x-1+y-1$,右下角的 $b=n-x+m-y$。

$b$ 就是最大的数字,$x$ 就是不满足 $cnt_i=4i$ 的第一个 $i$(显然)。

然后我们爆枚 $n$,算出 $m$,推出 $y$,然后检查一下就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int T, a[1000005], cnt[1000005], mx, aa, bb, d[1000005], n, m, xx, yy;
bool chk(int q){
n = q;
m = T / n;
yy = n + m - xx - mx;
memset(d, 0, sizeof(d));
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++){
int t=abs(i-xx)+abs(j-yy);
d[t]++;
}
for(int i=0; i<T; i++)
if(d[i]!=cnt[i])
return false;
return true;
}
int main(){
cin>>T;
for(int i=1; i<=T; i++){
scanf("%d", &a[i]);
cnt[a[i]]++;
mx = max(mx, a[i]);
}
for(xx=1; xx<T; xx++)
if(cnt[xx]<xx*4)
break;
for(int i=1; i<=T; i++)
if(T%i==0 && chk(i)){
cout<<n<<" "<<m<<endl<<xx<<" "<<yy<<endl;
return 0;
}
cout<<"-1\n";
return 0;
}