# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
321662 | daniel920712 | The Kingdom of JOIOI (JOI17_joioi) | C++14 | 4083 ms | 100724 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
using namespace std;
int all[2005][2005];
int l1[2005],r1[2005];
int l2[2005],r2[2005];
map < int , vector < pair < int , int > > > where;
int main()
{
int small=2e9,big=0,l,r,N,M,ok,x,y,a,b,c,d,i,j,k;
scanf("%d %d",&N,&M);
for(i=0;i<N;i++)
{
for(j=0;j<M;j++)
{
scanf("%d",&all[i][j]);
where[all[i][j]].push_back(make_pair(i,j));
small=min(small,all[i][j]);
big=max(big,all[i][j]);
}
}
l=0;
r=(big-small+1);
while((r-l)>1)
{
ok=1;
for(auto i:where)
{
if(i.first>small+(r+l)/2) if(big-i.first>(r+l)/2) ok=0;
if(i.first<big-(r+l)/2) if(i.first-small>(r+l)/2) ok=0;
}
if(ok==0)
{
l=(r+l)/2;
continue;
}
for(i=0;i<N;i++)
{
l1[i]=l2[i]=M;
r1[i]=r2[i]=-1;
}
for(auto i:where)
{
for(auto j:i.second)
{
if(i.first>small+(r+l)/2)
{
l1[j.first]=min(l1[j.first],j.second);
r1[j.first]=max(r1[j.first],j.second);
}
if(i.first<big-(r+l)/2)
{
l2[j.first]=min(l2[j.first],j.second);
r2[j.first]=max(r2[j.first],j.second);
}
}
}
a=b=c=d=1;
x=M;
for(i=0;i<N;i++)
{
x=min(x,l1[i]);
if(x<=r2[i]) a=0;
}
x=-1;
for(i=0;i<N;i++)
{
x=max(x,r2[i]);
if(x>=l1[i]) b=0;
}
x=M;
for(i=0;i<N;i++)
{
x=min(x,l2[i]);
if(x<=r1[i]) c=0;
}
x=-1;
for(i=0;i<N;i++)
{
x=max(x,r1[i]);
if(x>=l2[i]) d=0;
}
if(a||b||c||d) r=(l+r)/2;
else l=(r+l)/2;
}
ok=1;
for(auto i:where)
{
if(i.first>small+l) if(big-i.first>l) ok=0;
if(i.first<big-l) if(i.first-small>l) ok=0;
}
if(ok==0)
{
printf("%d\n",r);
return 0;
}
for(i=0;i<N;i++)
{
l1[i]=l2[i]=M;
r1[i]=r2[i]=-1;
}
for(auto i:where)
{
for(auto j:i.second)
{
if(i.first>small+l)
{
l1[j.first]=min(l1[j.first],j.second);
r1[j.first]=max(r1[j.first],j.second);
}
if(i.first<big-l)
{
l2[j.first]=min(l2[j.first],j.second);
r2[j.first]=max(r2[j.first],j.second);
}
}
}
a=b=c=d=1;
x=M;
for(i=0;i<N;i++)
{
x=min(x,l1[i]);
if(x<=r2[i]) a=0;
}
x=-1;
for(i=0;i<N;i++)
{
x=max(x,r2[i]);
if(x>=l1[i]) b=0;
}
x=M;
for(i=0;i<N;i++)
{
x=min(x,l2[i]);
if(x<=r1[i]) c=0;
}
x=-1;
for(i=0;i<N;i++)
{
x=max(x,r1[i]);
if(x>=l2[i]) d=0;
}
if(a||b||c||d) printf("%d\n",l);
else printf("%d\n",r);
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |