Submission #876287

#	Time	Username	Problem	Language	Result	Execution time	Memory
876287		ReLice	The Kingdom of JOIOI (JOI17_joioi)	C++14	0 / 100	2 ms	6492 KiB

joioi

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define endl "\n"
#define fr first
#define sc second
#define sz size()
#define ins insert
#define bc back()
#define str string
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
void start(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
const ll inf=1e18+7;
const ll mod=1e9;
const ll N=2e3+7;
const ld eps=1e-9;
ll xx[4]={1,-1,0,0},yy[4]={0,0,1,-1};
bool vis[N][N],good[N][N],need[N][N];
ll a[N][N],mx=0,mn=inf;
ll n,m;
ll i,j;
ll bfs(ll x,ll y){
	ll c=0;
	queue<pair<ll,ll>> q;
	q.push({x,y});
	vis[x][y]=true;
	while(q.sz){
		ll x=q.front().fr,y=q.front().sc;
		if(need[x][y])c++;
		q.pop();
		for(i=0;i<4;i++){
			if(good[x+xx[i]][y+yy[i]] && !vis[x+xx[i]][y+yy[i]]){
				q.push({x+xx[i],y+yy[i]});
				vis[x+xx[i]][y+yy[i]]=true;
			}
		}
	}
	return c;
}
bool check(ll mid){
	ll x,y,c=0;
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			if(a[i][j]<mx-mid){
				x=i;
				y=j;
				c++;
				need[i][j]=true;
			}else need[i][j]=false;
			if(a[i][j]<=mn+mid)good[i][j]=true;
			else good[i][j]=false;
			vis[i][j]=false;
		}
	}
	if(c!=bfs(x,y))return false;
	c=0;
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			if(a[i][j]>mn+mid){
				x=i;
				y=j;
				c++;
				need[i][j]=true;
			}else need[i][j]=false;
			if(a[i][j]>=mx-mid) good[i][j]=true;
			else good[i][j]=false;
			vis[i][j]=false;
		}
	}
	if(c!=bfs(x,y))return false;
	vector<ll> v;
	for(i=1;i<=n;i++){
		x=a[i][1];
		if(x>mn+mid)v.pb(1);
		else if(x<mx-mid)v.pb(2);
		else v.pb(0);
	}
	for(i=2;i<=m;i++){
		x=a[n][i];
		if(x>mn+mid)v.pb(1);
		else if(x<=mx-mid)v.pb(2);
		else v.pb(0);
	}
	for(i=n-1;i>0;i--){
		x=a[i][m];
		if(x>mn+mid)v.pb(1);
		else if(x<=mx-mid)v.pb(2);
		else v.pb(0);
	}
	for(i=m-1;i>0;i--){
		x=a[1][i];
		if(x>mn+mid)v.pb(1);
		else if(x<=mx-mid)v.pb(2);
		else v.pb(0);
	}
	c=0;
	x=0;
	for(i=0;i<(ll)v.sz-1;i++){
		if(i<v.sz-2 && v[i]==1 && x==2) c++;
		if(v[i])x=v[i];
	}
	if(x>0){
		for(i=0;i<(ll)v.sz-1;i++){
			if(v[i]){
				if(v[i]!=x)c++;
				else break;
			}
		}
	}
	if(c>1)return false;
	return true;
}
void solve(){
    cin>>n>>m;
    for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			cin>>a[i][j];
			mx=max(mx,a[i][j]);
			mn=min(mn,a[i][j]);
		}
	}
	if(mn==mx){
		cout<<0<<endl;
		return;
	}
	ll l=0,r=mx-mn;
	while(r-l>1){
		ll mid=(l+r)/2;
		if(check(mid))r=mid;
		else l=mid;
	}
	cout<<r<<endl;
}

signed main(){
    start();
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    ll t=1;
    //cin>>t;
    while(t--) solve();
}
/*









*/

Compilation message (stderr)

joioi.cpp: In function 'bool check(long long int)':
joioi.cpp:111:7: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |   if(i<v.sz-2 && v[i]==1 && x==2) c++;
      |      ~^~~~~~~
joioi.cpp: In function 'void fre(std::string)':
joioi.cpp:19:27: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 | void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
      |                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
joioi.cpp:19:64: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 | void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
      |                                                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
joioi.cpp: In function 'bool check(long long int)':
joioi.cpp:67:11: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
   67 |  if(c!=bfs(x,y))return false;
      |        ~~~^~~~~
joioi.cpp:67:11: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]

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