oj.uz

Submission #536912

# Submission time Handle Problem Language Result Execution time Memory
536912 2022-03-14T07:20:57 Z pavement The Kingdom of JOIOI (JOI17_joioi) C++17
100 / 100
 2133 ms 101896 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using db = double;
using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using iiii = tuple<int, int, int, int>;
template<class key, class value = null_type, class cmp = less<key> >
using ordered_set = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;

int tans = LLONG_MAX, H, W, _A[2005][2005], A[2005][2005], lim[2005];

int solve() {
	int lo = 0, hi = 1e9, ans = -1;
	iii mx = mt(0, 0, 0);
	for (int i = 1; i <= H; i++)
		for (int j = 1; j <= W; j++)
			mx = max(mx, mt(A[i][j], i, j));
	while (lo <= hi) {
		int mid = (lo + hi) / 2, mi2 = 1e9, mx2 = 0;
		for (int i = 1; i <= H; i++) {
			lim[i] = W + 1;
			for (int j = 1; j <= W; j++)
				if (g0(mx) - A[i][j] > mid) {
					lim[i] = j;
					break;
				}
			lim[i]--;
		}
		for (int j = H - 1; j >= 1; j--) lim[j] = min(lim[j], lim[j + 1]);
		bool inv = lim[g1(mx)] < g2(mx);
		for (int i = 1; i <= H; i++)
			for (int j = lim[i] + 1; j <= W; j++)
				mi2 = min(mi2, A[i][j]), mx2 = max(mx2, A[i][j]);
		inv |= mx2 - mi2 > mid;
		if (inv) lo = mid + 1;
		else ans = mid, hi = mid - 1;
	}
	assert(ans != -1);
	return ans;
}

void reflect_hor() {
	for (int i = 1; i <= H; i++)
		for (int j = 1; j <= W; j++)
			_A[i][j] = A[i][j];
	for (int i = 1; i <= H; i++)
		for (int j = 1; j <= W; j++)
			A[i][j] = _A[i][W - j + 1];
}

void rotate_90() {
	for (int i = 1; i <= H; i++)
		for (int j = 1; j <= W; j++)
			_A[i][j] = A[i][j];
	for (int i = 1; i <= W; i++)
		for (int j = 1; j <= H; j++)
			A[i][j] = _A[H - j + 1][i];
	swap(H, W);
}

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> H >> W;
	for (int i = 1; i <= H; i++)
		for (int j = 1; j <= W; j++)
			cin >> A[i][j];
	for (int k = 0; k < 4; k++) {
		tans = min(tans, solve());
		reflect_hor();
		tans = min(tans, solve());
		reflect_hor();
		rotate_90();
	}
	cout << tans << '\n';
}

Compilation message

joioi.cpp:80:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   80 | main() {
      | ^~~~

Subtask #1
15.0 / 15.0

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

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 2004 KB Output is correct
16 Correct 11 ms 2644 KB Output is correct
17 Correct 14 ms 2768 KB Output is correct
18 Correct 15 ms 2840 KB Output is correct
19 Correct 14 ms 2788 KB Output is correct
20 Correct 12 ms 2804 KB Output is correct
21 Correct 18 ms 2900 KB Output is correct
22 Correct 17 ms 2960 KB Output is correct
23 Correct 19 ms 2956 KB Output is correct
24 Correct 15 ms 2824 KB Output is correct
25 Correct 21 ms 2964 KB Output is correct
26 Correct 23 ms 2944 KB Output is correct
27 Correct 25 ms 2932 KB Output is correct
28 Correct 20 ms 2912 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 2004 KB Output is correct
16 Correct 11 ms 2644 KB Output is correct
17 Correct 14 ms 2768 KB Output is correct
18 Correct 15 ms 2840 KB Output is correct
19 Correct 14 ms 2788 KB Output is correct
20 Correct 12 ms 2804 KB Output is correct
21 Correct 18 ms 2900 KB Output is correct
22 Correct 17 ms 2960 KB Output is correct
23 Correct 19 ms 2956 KB Output is correct
24 Correct 15 ms 2824 KB Output is correct
25 Correct 21 ms 2964 KB Output is correct
26 Correct 23 ms 2944 KB Output is correct
27 Correct 25 ms 2932 KB Output is correct
28 Correct 20 ms 2912 KB Output is correct
29 Correct 1569 ms 85216 KB Output is correct
30 Correct 1476 ms 84656 KB Output is correct
31 Correct 1554 ms 86284 KB Output is correct
32 Correct 1607 ms 86164 KB Output is correct
33 Correct 1454 ms 82748 KB Output is correct
34 Correct 1629 ms 86280 KB Output is correct
35 Correct 2133 ms 101788 KB Output is correct
36 Correct 1860 ms 96376 KB Output is correct
37 Correct 2117 ms 101896 KB Output is correct