oj.uz

Submission #39578

# Submission time Handle Problem Language Result Execution time Memory
39578 2018-01-16T15:53:21 Z comtalyst The Kingdom of JOIOI (JOI17_joioi) C++14
0 / 100
 0 ms 41280 KB 
/*
 *	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=m,i,j;
	for(i = 1; i <= n; i++){
		x = 1;
		for(j = 1; j <= m; j++){
			tmp[x][y] = field[i][j];
			x++;
		}
		y--;
	}
	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++){
			ok = true;
			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;
					}
				}
			}
			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

joioi.cpp:58:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
joioi.cpp: In function 'int main()':
joioi.cpp:59: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:59: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:59: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:59: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:59: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:59: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:63: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:66: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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 41280 KB Output is correct
2 Incorrect 0 ms 41280 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 41280 KB Output is correct
2 Incorrect 0 ms 41280 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 41280 KB Output is correct
2 Incorrect 0 ms 41280 KB Output isn't correct
3 Halted 0 ms 0 KB -