Submission #50712

#	Time	Username	Problem	Language	Result	Execution time	Memory
50712		MatheusLealV	The Kingdom of JOIOI (JOI17_joioi)	C++17	100 / 100	3460 ms	95144 KiB

joioi

#include <bits/stdc++.h>
#define N 2002
using namespace std;

struct ponto {
	int x, y, val;
};

vector < ponto > P;

inline bool op(ponto a, ponto b){
	return a.val < b.val;
}

int n, m, mat[N][N], A[N][N], B[N][N];

inline int rightmost(int val)
{
	int ini = 0, fim = P.size() - 1, mid, best;

	while(fim >= ini)
	{
		mid = (ini + fim)/2;

		if(P[mid].val - P[0].val <= val) ini = mid + 1, best = mid;

		else fim = mid - 1;
	}

	return best;
}

inline int leftmost(int val)
{
	int ini = 0, fim = P.size() - 1, mid, best;

	while(fim >= ini)
	{
		mid = (ini + fim)/2;

		if(P.back().val - P[mid].val <= val) fim = mid - 1, best = mid;

		else ini = mid + 1;
	}

	return best;
}

inline bool check1()
{
	bool E = 1, D = 1;

	int maior = 0;

	for(int i = n; i >= 1; i--)
	{
		for(int j = 1; j <= m; j++)
			if(A[i][j]) maior = max(maior, j);

		for(int j = 1; j <= maior; j++)
			if(B[i][j]) E = 0;
	}

	maior = 0;

	for(int i = n; i >= 1; i--)
	{
		for(int j = 1; j <= m; j++)
			if(B[i][j]) maior = max(maior, j);

		for(int j = 1; j <= maior; j++)
			if(A[i][j]) D = 0;
	}

	return (E || D);
}

inline bool check2()
{
	int maior = 0, E = 1, D = 1;

	for(int i = 1; i <= n; i ++)
	{
		for(int j = 1; j <= m; j++)
			if(A[i][j]) maior = max(maior, j);

		for(int j = 1; j <= maior; j++)
			if(B[i][j]) E = 0;
	}

	maior = 0;

	for(int i = 1; i <= n; i ++)
	{
		for(int j = 1; j <= m; j++)
			if(B[i][j]) maior = max(maior, j);

		for(int j = 1; j <= maior; j++)
			if(A[i][j]) D = 0;
	}

	return (E || D);
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	cin>>n>>m;

	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			cin>>mat[i][j], P.push_back({i, j, mat[i][j]});

	sort(P.begin(), P.end(), op);

	int ini = 0, fim = 1e9, mid, best = -1;

	while(fim >= ini)
	{
		mid = (ini + fim)/2;

		int L = leftmost(mid), R = rightmost(mid);

		memset(A, 0, sizeof A), memset(B, 0, sizeof B);

		if(L <= R || R == L - 1)
		{
			if(R == L - 1) swap(L, R);

			for(int i = 0; i < L; i++)
			{
				int x = P[i].x, y = P[i].y;

				A[x][y] ++;
			}

			for(int i = R + 1; i < P.size(); i++)
			{
				int x = P[i].x, y = P[i].y;

				B[x][y] ++;
			}

			if(check1() || check2())
			{
				best = mid;

				fim = mid - 1;
			}

			else ini = mid + 1;
		}

		else ini = mid + 1;
	}

	cout<<best<<"\n";
}

Compilation message (stderr)

joioi.cpp: In function 'int main()':
joioi.cpp:138:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = R + 1; i < P.size(); i++)
                       ~~^~~~~~~~~~
joioi.cpp:35:40: warning: 'best' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int ini = 0, fim = P.size() - 1, mid, best;
                                        ^~~~
joioi.cpp:129:4: warning: 'best' may be used uninitialized in this function [-Wmaybe-uninitialized]
    if(R == L - 1) swap(L, R);
    ^~

• Subtask 1: 15 / 15
• Subtask 2: 45 / 45
• Subtask 3: 40 / 40