oj.uz

Submission #111976

# Submission time Handle Problem Language Result Execution time Memory
111976 2019-05-17T03:15:55 Z qkxwsm The Kingdom of JOIOI (JOI17_joioi) C++14
0 / 100
 4 ms 512 KB 
//clever
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define DBG(x) cerr << #x << " = " << (x) << endl
#define SZ(x) ((int) ((x).size()))
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)

#define INF 1000000007
#define MAXN 2013

typedef pair<int, int> pii;

int N, M;
int grid[MAXN][MAXN];
int big, small = INF;
pii bigpos, smallpos;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};
pii range[MAXN];


pii dsu[2][MAXN][MAXN];
pii get(bool f, pii p)
{
	if (dsu[f][p.fi][p.se] == p) return p;
	dsu[f][p.fi][p.se] = get(f, dsu[f][p.fi][p.se]);
	return dsu[f][p.fi][p.se];
}
void merge(bool f, pii a, pii b)
{
	a = get(f, a);
	b = get(f, b);
	dsu[f][a.fi][a.se] = b;
}
void init()
{
	FOR(i, 0, N)
	{
		FOR(j, 0, M)
		{
			dsu[0][i][j] = {i, j};
			dsu[1][i][j] = {i, j};
		}
	}
}

bool valid(int x, int y)
{
	return (0 <= x && x < N && 0 <= y && y < M);
}

bool ok()
{
	//these are the first guys that do not approve!
	FOR(i, 0, N)
	{
		if (range[i].fi >= range[i].se) return false;
	}
	bool flag = true; int pos = 0;
	FOR(i, 0, N)
	{
		//the guy can be in the range (range[i].fi, range[i].se)
		if (range[i].se < pos)
		{
			flag = false; break;
		}
		pos = max(pos, range[i].fi);
	}
	if (flag) return true;
	flag = true; pos = M - 1;
	FOR(i, 0, N)
	{
		if (range[i].fi > pos)
		{
			flag = false; break;
		}
		pos = min(pos, range[i].se);
	}
	if (flag) return true;
	return false;
}
bool check(int x)
{
	init();
	FOR(i, 0, N)
	{
		FOR(j, 0, M)
		{
			if (grid[i][j] > small + x) continue;
			FOR(k, 0, 2)
			{
				pii p = {i + dx[k], j + dy[k]};
				if (valid(p.fi, p.se) && grid[p.fi][p.se] <= small + x)
				{
					merge(0, {i, j}, p);
				}
			}
		}
	}
	FOR(i, 0, N)
	{
		FOR(j, 0, M)
		{
			if (grid[i][j] < big - x) continue;
			FOR(k, 0, 2)
			{
				pii p = {i + dx[k], j + dy[k]};
				if (valid(p.fi, p.se) && grid[p.fi][p.se] >= big - x)
				{
					merge(1, {i, j}, p);
				}
			}
		}
	}
	//try to have SMALL be an increasing/decreasing sequence!
	FOR(i, 0, N)
	{
		for (range[i].se = 0; range[i].se < M; range[i].se++)
		{
			if (get(0, {i, range[i].se}) != get(0, smallpos)) break;
		}
		for (range[i].fi = M - 1; range[i].fi >= 0; range[i].fi--)
		{
			if (get(1, {i, range[i].fi}) != get(1, bigpos)) break;
		}
	}
	// if (x == 0)
	// {
	// 	FOR(i, 0, N)
	// 	{
	// 		cerr << range[i].fi << ',' << range[i].se << endl;
	// 	}
	// }
	if (ok())
	{
		return true;
	}
	//try to have BIG be an increasing/decreasing sequence
	FOR(i, 0, N)
	{
		for (range[i].se = 0; range[i].se < M; range[i].se++)
		{
			if (get(1, {i, range[i].se}) != get(1, bigpos)) break;
		}
		for (range[i].fi = M - 1; range[i].fi >= 0; range[i].fi--)
		{
			if (get(0, {i, range[i].fi}) != get(0, smallpos)) break;
		}
	}
	if (ok())
	{
		return true;
	}
	return false;
}

int32_t main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	// cout << fixed << setprecision(10);
	// cerr << fixed << setprecision(10);
	// if (fopen("file.in", "r"))
	// {
	// 	freopen ("file.in", "r", stdin);
	// 	freopen ("file.out", "w", stdout);
	// }
	cin >> N >> M;
	FOR(i, 0, N)
	{
		FOR(j, 0, M)
		{
			cin >> grid[i][j];
			if (grid[i][j] > big)
			{
				big = grid[i][j];
				bigpos = {i, j};
			}
			if (grid[i][j] < small)
			{
				small = grid[i][j];
				smallpos = {i, j};
			}
		}
	}
	// cerr << smallpos.fi << ' ' << smallpos.se << ' ' << bigpos.fi << ' ' << bigpos.se << endl;
	int lo = 0, hi = big - small;
	while(hi > lo)
	{
		int mid = (hi + lo) >> 1;
		if (check(mid)) hi = mid;
		else lo = mid + 1;
	}
	cout << lo << '\n';
	// cerr << "time elapsed = " << (clock() / (CLOCKS_PER_SEC / 1000)) << " ms" << endl;
	return 0;
}
/* READ READ READ
* int overflow, maxn too small, special cases (n=1?, two distinct?), cin.tie() interactive
* reread the problem, try small cases
* note down possible sources of error as you go
* do smth instead of nothing
*/

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 3 ms 512 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 4 ms 512 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Incorrect 3 ms 512 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 3 ms 512 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 4 ms 512 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Incorrect 3 ms 512 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 3 ms 512 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 4 ms 512 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Incorrect 3 ms 512 KB Output isn't correct
13 Halted 0 ms 0 KB -