Submission #111982

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
111982	2019-05-17T03:27:41 Z	qkxwsm	The Kingdom of JOIOI (JOI17_joioi)	C++14	60 / 100	4000 ms	97596 KB

joioi

//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 + 1);
	}
	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 - 1);
	}
	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 (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

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	3 ms	512 KB	Output is correct
3	Correct	4 ms	512 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	3 ms	512 KB	Output is correct
6	Correct	3 ms	512 KB	Output is correct
7	Correct	2 ms	512 KB	Output is correct
8	Correct	3 ms	512 KB	Output is correct
9	Correct	0 ms	484 KB	Output is correct
10	Correct	3 ms	512 KB	Output is correct
11	Correct	13 ms	512 KB	Output is correct
12	Correct	2 ms	512 KB	Output is correct
13	Correct	3 ms	512 KB	Output is correct
14	Correct	3 ms	384 KB	Output is correct

Subtask #2

45.0 / 45.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	3 ms	512 KB	Output is correct
3	Correct	4 ms	512 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	3 ms	512 KB	Output is correct
6	Correct	3 ms	512 KB	Output is correct
7	Correct	2 ms	512 KB	Output is correct
8	Correct	3 ms	512 KB	Output is correct
9	Correct	0 ms	484 KB	Output is correct
10	Correct	3 ms	512 KB	Output is correct
11	Correct	13 ms	512 KB	Output is correct
12	Correct	2 ms	512 KB	Output is correct
13	Correct	3 ms	512 KB	Output is correct
14	Correct	3 ms	384 KB	Output is correct
15	Correct	4 ms	640 KB	Output is correct
16	Correct	14 ms	3584 KB	Output is correct
17	Correct	148 ms	3920 KB	Output is correct
18	Correct	65 ms	3840 KB	Output is correct
19	Correct	84 ms	3932 KB	Output is correct
20	Correct	83 ms	3448 KB	Output is correct
21	Correct	190 ms	3968 KB	Output is correct
22	Correct	94 ms	3968 KB	Output is correct
23	Correct	100 ms	3968 KB	Output is correct
24	Correct	99 ms	3584 KB	Output is correct
25	Correct	125 ms	3968 KB	Output is correct
26	Correct	226 ms	4088 KB	Output is correct
27	Correct	219 ms	4088 KB	Output is correct
28	Correct	201 ms	3968 KB	Output is correct

Subtask #3

0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	3 ms	512 KB	Output is correct
3	Correct	4 ms	512 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	3 ms	512 KB	Output is correct
6	Correct	3 ms	512 KB	Output is correct
7	Correct	2 ms	512 KB	Output is correct
8	Correct	3 ms	512 KB	Output is correct
9	Correct	0 ms	484 KB	Output is correct
10	Correct	3 ms	512 KB	Output is correct
11	Correct	13 ms	512 KB	Output is correct
12	Correct	2 ms	512 KB	Output is correct
13	Correct	3 ms	512 KB	Output is correct
14	Correct	3 ms	384 KB	Output is correct
15	Correct	4 ms	640 KB	Output is correct
16	Correct	14 ms	3584 KB	Output is correct
17	Correct	148 ms	3920 KB	Output is correct
18	Correct	65 ms	3840 KB	Output is correct
19	Correct	84 ms	3932 KB	Output is correct
20	Correct	83 ms	3448 KB	Output is correct
21	Correct	190 ms	3968 KB	Output is correct
22	Correct	94 ms	3968 KB	Output is correct
23	Correct	100 ms	3968 KB	Output is correct
24	Correct	99 ms	3584 KB	Output is correct
25	Correct	125 ms	3968 KB	Output is correct
26	Correct	226 ms	4088 KB	Output is correct
27	Correct	219 ms	4088 KB	Output is correct
28	Correct	201 ms	3968 KB	Output is correct
29	Execution timed out	4033 ms	97596 KB	Time limit exceeded
30	Halted	0 ms	0 KB	-