Codeforces Round #495 (Div. 2) Sonya and Matrix

正常没有正方形的限制下，值为i的点个数4i

那么从0开始遍历，第一个不为4i的值就是min(x, y)

由于对称性我们姑且令x为这个值

我们先列举n*m=t的各种情况

对于一对n, m。我们已经知道n,m,x

再由于对称性，我们假设距离(x,y)最远的点在(n, m)。(当然也可能在(1,m))

现在知道了(n,m)到(x,y)为max(a[I])

列方程就能求出y了

然后再暴力验证就好了

#include <iostream>

#include <cstdio>

#include <cmath>

#include <cstring>

#include <map>

using namespace std;

const int N = 1e6 + 5;

const int INF = 0x3f3f3f3f;

typedef long long ll;

#define lson l, m, rt<<1

#define rson m+1, r, rt<<1|1

int A[N];

int mp[N];

int maxNum;

struct Line{

    int k, b;

    Line(int a=0, int _b=0):k(a), b(_b){}

    int Count(int x1, int x2, int y1, int y2) {

        int L = k*x1 + b;

        int R = k*x2 + b;

        if(L > R) swap(L, R);

        x1 = L; x2 = R;

        if(y1 < x1) {

            if(y2 < x1) return 0;

            else if(y2 <= x2)

                return y2 - x1 + 1;

            else return x2 - x1 + 1;

        } else if(y1 <= x2) {

            if(y2 <= x2)

                return y2 - y1 + 1;

            else return x2 - y1 + 1;

        } else

            return 0;

    }

};

bool Test(int n, int m, int x) {

    if(n < 2*x-1 || m < 2*x-1)

        return false;

    int y = n + m - maxNum - x;

    if(y < x || m - y < x - 1)

        return false;

//    printf("%d %d\n", n, m);

    for(int i = x; i <= maxNum; ++i) {

        int all = 0;

        int l1 = max(1, x - i);

        int l2 = min(n, x + i);

        int r1 = max(1, y - i);

        int r2 = min(m, y + i);

        Line t1(-1, i+x+y);

        all += t1.Count(l1, l2, r1, r2);

        Line t2(1, i-x+y);

        all += t2.Count(l1, l2, r1, r2);

        Line t3(-1, -i+x+y);

        all += t3.Count(l1, l2, r1, r2);

        Line t4(1, -i-x+y);

        all += t4.Count(l1, l2, r1, r2);

    //    printf("%d ", all);

        if(n - x >= i) all --;

        if(y > i) all --;

        if(m - y >= i) all --;

    //    printf("%d %d\n", i, all);

        if(all != mp[i])

            return false;

    }

    std::printf("%d %d\n%d %d\n", n, m, x, y);

    return true;

}

int main() {

    int t;

    while(~scanf("%d", &t)) {

        memset(mp, 0, sizeof(mp));

        maxNum = -1;

        for(int i = 0; i < t; ++i) {

            scanf("%d", &A[i]);

            mp[A[i]] ++;

            maxNum = max(maxNum, A[i]);

        }

        bool flag = true; int X;

        for(int i = 0; ; ++i) {

            int id = i; int num = mp[i];

            if(id == 0) {

                flag &= num == 1;

            } else {

                flag &= num == 4*i;

            }

            if(flag == false) {

                X = i;

                break;

            }

        }

        // for(int i = 0; i < t; ++i) printf("%d ", mp[i]); printf("\n");

        // printf("%d\n", X);

        if(X == 0) {

            printf("-1\n");

            continue;

        }

        flag = false;

        for(int i = 1; i <= sqrt(t) && !flag; ++i) {

            if(t % i == 0) {

                int n = i; int m = t / i;

                flag = Test(n, m, X);

                if(!flag) {

                    flag = Test(m, n, X);

                }

            }

        }

        if(!flag) {

            printf("-1\n");

        }

    }

    return 0;

}