Submission #233372

#	Time	Username	Problem	Language	Result	Execution time	Memory
233372		nicolaalexandra	The Kingdom of JOIOI (JOI17_joioi)	C++14	60 / 100	4066 ms	114468 KiB

joioi

#include <bits/stdc++.h>
#define DIM 2010
#define DIMBUFF 30000000
#define INF 2000000000
using namespace std;
int a[DIM][DIM],b[DIM][DIM],viz[DIM][DIM];
struct idk{
    int val,l,c;
} v[DIM*DIM];
deque <pair<int,int> > c;
int di[] = {-1,1,0,0};
int dj[] = {0,0,-1,1};
int n,m,i,j,sol,mini,maxi,k,pos;
char buff[DIMBUFF];

int verif (int val){

    /// toate valorile < maxi - val trb puse in zona minimelor
    /*for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            viz[i][j] = 0;*/
    memset (viz,0,sizeof viz);

    for (int i=1;i<=k;++i){
        if (v[i].val >= maxi - val)
            break;
        int lin = v[i].l, col = v[i].c;
        if (viz[lin][col])
            continue;

        c.clear();
        c.push_back(make_pair(lin,col));
        viz[lin][col] = 1;
        while (!c.empty()){
            int ic = c.front().first;
            int jc = c.front().second;
            c.pop_front();
            for (int dir=0;dir<=3;++dir){
                int iv = ic + di[dir];
                int jv = jc + dj[dir];
                if (iv >= lin && iv <= n && jv >= 1 && jv <= col && !viz[iv][jv]){
                    viz[iv][jv] = 1;
                    c.push_back(make_pair(iv,jv));
                }}}}

    int maxim = 0, maxim2 = 0, minim = INF, minim2 = INF;
    for (int i=1;i<=n;++i)
        for (int j=1;j<=m;++j){
            if (viz[i][j]){
                minim = min (minim,a[i][j]);
                maxim = max (maxim,a[i][j]);
            } else {
                minim2 = min (minim2,a[i][j]);
                maxim2 = max (maxim2,a[i][j]);
            }}

    if (max (maxim - minim, maxim2 - minim2) > val)
        return 0;
    return 1;
}

void solve (){

    int st = 0, dr = maxi - mini, val;
    while (st <= dr){
        int mid = (st+dr)>>1;
        if (verif (mid)){
            val = mid;
            dr = mid-1;
        } else st = mid+1;
    }

    sol = min (sol,val);

}

inline int cmp (idk a, idk b){
    return a.val < b.val;
}

void roteste(){

    for (i=1;i<=n;++i)
        for (j=1;j<=m;++j)
            b[m-j+1][i] = a[i][j];
    swap (n,m);

    k = 0;
    for (i=1;i<=n;++i)
        for (j=1;j<=m;++j){
            a[i][j] = b[i][j];
            v[++k] = {a[i][j],i,j};
        }
    sort (v+1,v+k+1,cmp);
}
int get_nr(){
    while (!(buff[pos] >= '0' && buff[pos] <= '9'))
        ++pos;
    int nr = 0;
    while (buff[pos] >= '0' && buff[pos] <= '9'){
        nr = nr*10 + buff[pos] - '0';
        ++pos;
    }
    return nr;
}
int main (){

    //FILE *fin = fopen ("date.in","r");
    //FILE *fout = fopen ("date.out","w");
    FILE *fin = stdin;
    FILE *fout = stdout;

    fread (buff,1,DIMBUFF,fin);
    //cin>>n>>m;
    n = get_nr(), m = get_nr();
    mini = INF;
    for (i=1;i<=n;++i)
        for (j=1;j<=m;++j){
            //cin>>a[i][j];
            a[i][j] = get_nr();
            mini = min (mini,a[i][j]);
            maxi = max (maxi,a[i][j]);
            v[++k] = {a[i][j],i,j};
        }

    sort (v+1,v+k+1,cmp);

    sol = INF;
    solve();

    roteste();
    solve();

    roteste();
    solve();

    roteste();
    solve();

    fprintf(fout,"%d",sol);

    return 0;
}

Compilation message (stderr)

joioi.cpp: In function 'int main()':
joioi.cpp:113:11: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     fread (buff,1,DIMBUFF,fin);
     ~~~~~~^~~~~~~~~~~~~~~~~~~~
joioi.cpp: In function 'void solve()':
joioi.cpp:64:35: warning: 'val' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int st = 0, dr = maxi - mini, val;
                                   ^~~

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