Submission #39584

#	Time	Username	Problem	Language	Result	Execution time	Memory
39584		comtalyst	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	1296 ms	88392 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
- bad rotation (forgot to swap n,m)
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[5][2005][2005],need[2005];

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[1][i][j]);
			mn = min(mn,{field[1][i][j],{i,j}});
			mx = max(mx,{field[1][i][j],{i,j}});
		}
	}
	for(k = 1; k <= 3; k++){
		x = 1;
		y = n;
		for(i = 1; i <= n; i++){
			x = 1;
			for(j = 1; j <= m; j++){
				field[k+1][x][y] = field[k][i][j];
				x++;
			}
			y--;
		}
		swap(n,m);
	}
	swap(n,m);
	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[k][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[k][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[k][i][j] > mn.x+mid){
						ok = false;
						break;
					}
				}
				lst = max(lst,need[i]);
				if(!ok) break;
			}
			if(ok){
				break;
			}
			swap(n,m);
		}
		if(k%2 == 0){
			swap(n,m);
		}
		if(ok){
			res = min(res,mid);
			r = mid-1;
		}
		else{
			l = mid+1;
		}
	}
	printf("%d\n",res);

	return 0;	
}

Compilation message (stderr)

joioi.cpp:42:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
joioi.cpp: In function 'int main()':
joioi.cpp:43: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:43: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:43: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:43: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:47: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:50:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&field[1][i][j]);
                               ^

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