Submission #233442

#	Time	Username	Problem	Language	Result	Execution time	Memory
233442		nicolaalexandra	The Kingdom of JOIOI (JOI17_joioi)	C++14	0 / 100	5 ms	512 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];
pair<int,int> c[DIM*DIM];
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){

    int last = 0;
    for (i=1;i<=n;i++){
        for (j=1;j<=m;j++){
            if (a[i][j] < maxi - val)
                last = j;
        }

        for (j=1;j<=m;j++)
            if (a[i][j] > mini + val && j <= last)
                return 0;
    }

    return 1;
}

void solve (){

    int st = 0, dr = maxi - mini, val = INF;
    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(){

    int idx = 0;
    for (i=1;i<=n;++i)
        for (j=1;j<=m;++j){
            b[m-j+1][i] = a[i][j];
            idx++;
            int l = v[idx].l, c = v[idx].c;
            v[idx].l = m-c+1;
            v[idx].c = l;
        }
    swap (n,m);

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

}
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:87: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);
     ~~~~~~^~~~~~~~~~~~~~~~~~~~

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