Submission #906043

#	Time	Username	Problem	Language	Result	Execution time	Memory
906043		andrei_iorgulescu	The Kingdom of JOIOI (JOI17_joioi)	C++17	100 / 100	2490 ms	86444 KiB

joioi

#include <bits/stdc++.h>

using namespace std;

int n,m,a[2005][2005],b[2005][2005],vmax = 0,vmin = 1e9;
int c[2005][2005];

bool frumoasa(int k)
{
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (a[i][j] < vmax - k)
                b[i][j] = 0;
            else if (a[i][j] > vmin + k)
                b[i][j] = 1;
            else
                b[i][j] = 2;
            if (a[i][j] < vmax - k and a[i][j] > vmin + k)
                return false;
        }
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            c[i][j] = 0;
    for (int i = 1; i <= n; i++)
    {
        int max0 = 0,min1 = 1e9;
        for (int j = 1; j <= m; j++)
        {
            if (b[i][j] == 0)
                max0 = j;
        }
        for (int j = m; j >= 1; j--)
        {
            if (b[i][j] == 1)
                min1 = j;
        }
        if (max0 > min1)
            return false;
        for (int j = 1; j <= max0; j++)
            c[i][j] = 1;
        for (int j = min1; j <= m; j++)
            c[i][j] = 2;
    }
    for (int j = 1; j <= m; j++)
    {
        int max0 = 0,min1 = 1e9;
        for (int i = 1; i <= n; i++)
        {
            if (b[i][j] == 0)
                max0 = i;
        }
        for (int i = n; i >= 1; i--)
        {
            if (b[i][j] == 1)
                min1 = i;
        }
        if (max0 > min1)
            return false;
        for (int i = 1; i <= max0; i++)
        {
            if (c[i][j] == 2)
                return false;
            c[i][j] = 1;
        }
        for (int i = min1; i <= n; i++)
        {
            if (c[i][j] == 1)
                return false;
            c[i][j] = 2;
        }
    }
    return true;
}

void invert_lins()
{
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m / 2; j++)
            swap(a[i][j],a[i][m - j + 1]);
}

void invert_cols()
{
    for (int j = 1; j <= m; j++)
        for (int i = 1; i <= n / 2; i++)
            swap(a[i][j],a[n - i + 1][j]);
}

bool pot(int k)
{
    ///pot face diferenta <= k?
    ///sa zicem ca cele mai mici o sa fie J-uri
    ///cele mai mari trebuie sa fie I
    ///pot pune J doar la valori <= Vmin + k
    ///pot pune I doar la valori >= Vmax - k
    ///atunci o sa fixez alea care pot fi doar J sau doar I, restul am libertate sa le pun oricum
    ///pot oare sa construiesc matricea a.i sa fie frumoasa?
    ///o matrice frumoasa arata din una din parti astfel: primul rand are prefix maxim de J, apoi ceva mai mic, etc etc etc
    if (frumoasa(k) == true)///normala
        return true;
    invert_lins();
    if (frumoasa(k) == true)///privita de la dr la st
        return true;
    invert_cols();
    if (frumoasa(k) == true)///privita complet pe dos
        return true;
    invert_lins();
    if (frumoasa(k) == true)///privita de jos in sus
        return true;
    return false;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j],vmax = max(vmax,a[i][j]),vmin = min(vmin,a[i][j]);
    int st = -1,pas = 1 << 29;
    while (pas != 0)
    {
        if (!pot(st + pas))
            st += pas;
        pas /= 2;
    }
    cout << st + 1;
    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 45 / 45
• Subtask 3: 40 / 40