Submission #39580

#	Time	Username	Problem	Language	Result	Execution time	Memory
39580		comtalyst	The Kingdom of JOIOI (JOI17_joioi)	C++14	60 / 100	4000 ms	41280 KiB

joioi

/*
 *	Task: JOI17_JOIOI
 *	Lang: C/C++11
 *	Author: comtalyst
 *	Site: oj.uz
 *	Last Update: 16/1/2018
 */

#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
using namespace std;

/* Note
----------------------------
Learned : 
Bugs found & solved :
- task description misunderstood
Optimizations :
----------------------------
*/	

#define x first
#define y second
#define umap unordered_map
#define pqueue priority_queue
#define mset multiset
#define mp make_pair
#define mt make_tuple
#define long long long
#define MOD 1000000007
#define MAX (int)2e9
#define MIN (int)-2e9
#define FILEIN_ freopen("__in.txt","r",stdin)
#define FILEOUT_ freopen("__out.txt","w",stdout)
#define FILEIN(text) freopen(text,"r",stdin)
#define FILEOUT(text) freopen(text,"w",stdout)

bool chk[2][2005][2005];
int n,m,field[2005][2005],tmp[2005][2005],need[2005];
void rotate(){
	int x=1,y=n,i,j;
	for(i = 1; i <= n; i++){
		x = 1;
		for(j = 1; j <= m; j++){
			tmp[x][y] = field[i][j];
			x++;
		}
		y--;
	}
	swap(n,m);
	for(i = 1; i <= n; i++){
		for(j = 1; j <= m; j++){
			field[i][j] = tmp[i][j];
		}
	}
}


main(){
	int t,i,j,k,x,y,l,r,mid,res=MAX,nx,ny,lst,v;
	bool ok;
	pair<int,pair<int,int>> mn={MAX,{MAX,MAX}},mx={MIN,{MIN,MIN}};
	
	scanf("%d %d",&n,&m);
	for(i = 1; i <= n; i++){
		for(j = 1; j <= m; j++){
			scanf("%d",&field[i][j]);
			mn = min(mn,{field[i][j],{i,j}});
			mx = max(mx,{field[i][j],{i,j}});
		}
	}
	l = 0; 
	r = mx.x-mn.x;
	while(l <= r){
		mid = (l+r)/2;
		for(k = 1; k <= 4; k++){
			for(i = 1; i <= n; i++){
				need[i] = 0;
				for(j = m; j >= 1; j--){
					if(field[i][j] < mx.x-mid){
						need[i] = j;
						break;
					}
				}
			}
			ok = true;
			lst = 0;
			for(i = 1; i <= n; i++){
				for(j = 1; j <= max(need[i],lst); j++){
					if(field[i][j] > mn.x+mid){
						ok = false;
						break;
					}
				}
				lst = max(lst,need[i]);
				if(!ok) break;
			}
			if(ok){
				break;
			}
			ok = true;
			lst = 0;
			for(i = n; i >= 1; i--){
				for(j = 1; j <= max(need[i],lst); j++){
					if(field[i][j] > mn.x+mid){
						ok = false;
						break;
					}
				}
				lst = max(lst,need[i]);
				if(!ok) break;
			}
			if(ok){
				break;
			}
			if(k < 4){
				rotate();
			}
		}

		if(ok){
			res = min(res,mid);
			r = mid-1;
		}
		else{
			l = mid+1;
		}
	}
	printf("%d\n",res);

	return 0;	
}

Compilation message (stderr)

joioi.cpp:59:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
joioi.cpp: In function 'int main()':
joioi.cpp:60:6: warning: unused variable 't' [-Wunused-variable]
  int t,i,j,k,x,y,l,r,mid,res=MAX,nx,ny,lst,v;
      ^
joioi.cpp:22:11: warning: unused variable 'first' [-Wunused-variable]
 #define x first
           ^
joioi.cpp:60:14: note: in expansion of macro 'x'
  int t,i,j,k,x,y,l,r,mid,res=MAX,nx,ny,lst,v;
              ^
joioi.cpp:23:11: warning: unused variable 'second' [-Wunused-variable]
 #define y second
           ^
joioi.cpp:60:16: note: in expansion of macro 'y'
  int t,i,j,k,x,y,l,r,mid,res=MAX,nx,ny,lst,v;
                ^
joioi.cpp:60:34: warning: unused variable 'nx' [-Wunused-variable]
  int t,i,j,k,x,y,l,r,mid,res=MAX,nx,ny,lst,v;
                                  ^
joioi.cpp:60:37: warning: unused variable 'ny' [-Wunused-variable]
  int t,i,j,k,x,y,l,r,mid,res=MAX,nx,ny,lst,v;
                                     ^
joioi.cpp:60:44: warning: unused variable 'v' [-Wunused-variable]
  int t,i,j,k,x,y,l,r,mid,res=MAX,nx,ny,lst,v;
                                            ^
joioi.cpp:64:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
                      ^
joioi.cpp:67:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&field[i][j]);
                            ^

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