oj.uz

답안 #68240

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
68240 2018-08-16T09:36:27 Z Nurlykhan The Kingdom of JOIOI (JOI17_joioi) C++17
0 / 100
 2 ms 376 KB 
#include <bits/stdc++.h>

#define pb push_back
#define all(v) v.begin(), v.end()
#define sz(v) int(v.size())
#define pii pair<int, int>
#define mp make_pair
#define f first
#define ll long long
#define ld long double
#define s second
#define vec vector<int>

using namespace std;

const int N = (int) 2e3 + 10;
const int M = (int) 2018 * 2018;
const int K = (int) 15;
const int INF = (int) 1e9 + 7;
const int mod = (int) 998244353;
const ld EPS = (ld) 1e-9;
const ll LINF = (ll) 1e18;

int n, m;
int a[N][N], ptr[N];
bool boo[N][N];

bool solve(int diff) {
	int mx_i = 1, mx_j = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (a[mx_i][mx_j] < a[i][j]) {
				mx_i = i;
				mx_j = j;
			}
		}
	}
	// a[mx_i][mx_j] <= a[i][j] + diff
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (a[mx_i][mx_j] <= diff + a[i][j]) {
				boo[i][j] = 1;
			} else {
				boo[i][j] = 0;
			}
		}
	}
	ptr[0] = m;
	for (int i = 1; i <= n; i++) {
		ptr[i] = ptr[i - 1];
		for (int j = 1; j <= ptr[i - 1]; j++) {
			if (!boo[i][j]) {
				ptr[i] = j - 1;
				break;
			}
		}
	}
	int mx = 0, mn = INF;
	for (int i = 1; i <= n; i++) {
		for (int j = ptr[i] + 1; j <= m; j++) {
			mx = max(mx, a[i][j]);
			mn = min(mn, a[i][j]);
		}
	}
	if (mx_j > ptr[mx_i]) 
		return false;
	return mx - mn <= diff;
}

void mirror() {
	for (int i = 1; i <= n / 2; i++) {
		for (int j = 1; j <= m; j++) {
			swap(a[i][j], a[n - i + 1][j]);
		}
	}
}

void rotate() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			a[j][n - i + 1] = a[i][j];
		}
	}
	swap(n, m);
}

bool ok(int diff) {
	bool ok = false;
	for (int i = 0; i < 4; i++) {
		ok |= solve(diff);
		mirror();
		ok |= solve(diff); 
		mirror();
		rotate();
	}
	return ok;
}

int main() {
	#ifdef sony
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	#endif
	srand(time(0));
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf("%d", &a[i][j]);
		}
	}
	int l = 1, r = INF;
	int ans;
	while (l <= r) {
		int mid = (l + r) / 2;
		if (ok(mid)) {
			r = mid - 1;
			ans = mid;
		} else {
			l = mid + 1;
		}
	}
	cout << ans;
	return 0;	
}

Compilation message

joioi.cpp: In function 'int main()':
joioi.cpp:108:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &a[i][j]);
    ~~~~~^~~~~~~~~~~~~~~~
joioi.cpp:122:7: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
  cout << ans;
  ~~~~~^~~~~~

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -