Submission #50711

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
50711	2018-06-13T03:55:01 Z	MatheusLealV	The Kingdom of JOIOI (JOI17_joioi)	C++17	100 / 100	3964 ms	289636 KB

joioi

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

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

vector < ponto > P;

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

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

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;
}

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;
}

int queryA(int xi, int yi, int xii, int yii) {
	return A[xii][yii] - A[xii][yi - 1] - A[xi - 1][yii] + A[xi - 1][yi - 1];
}

int queryB(int xi, int yi, int xii, int yii) {
	return B[xii][yii] - B[xii][yi - 1] - B[xi - 1][yii] + B[xi - 1][yi - 1];
}

int M[N][N], M2[N][N];

bool check1() // INDEXADO NA ESQUERDA-CIMA
{
	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);
}

bool check2() // INDEXADO NA ESQUERDA-BAIXO
{
	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);

		memset(M, 0, sizeof M);

		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;

			/*for(int i = 1; i <= n; i++)
				for(int j = 1; j <= m; j++)
				{
					A[i][j] += A[i - 1][j] + A[i][j - 1] - A[i - 1][j - 1];

					B[i][j] += B[i - 1][j] + B[i][j - 1] - B[i - 1][j - 1];
				}*/
		}

		else ini = mid + 1;
	}

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

Compilation message

joioi.cpp: In function 'int main()':
joioi.cpp:150:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = R + 1; i < P.size(); i++)
                       ~~^~~~~~~~~~
joioi.cpp: In function 'int rightmost(int)':
joioi.cpp:30:9: warning: 'best' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return best;
         ^~~~
joioi.cpp: In function 'int leftmost(int)':
joioi.cpp:46:9: warning: 'best' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return best;
         ^~~~

Subtask #1
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	379 ms	49784 KB	Output is correct
2	Correct	364 ms	49840 KB	Output is correct
3	Correct	371 ms	49840 KB	Output is correct
4	Correct	384 ms	49960 KB	Output is correct
5	Correct	362 ms	50012 KB	Output is correct
6	Correct	358 ms	50212 KB	Output is correct
7	Correct	368 ms	50212 KB	Output is correct
8	Correct	370 ms	50212 KB	Output is correct
9	Correct	382 ms	50260 KB	Output is correct
10	Correct	374 ms	50260 KB	Output is correct
11	Correct	369 ms	50268 KB	Output is correct
12	Correct	367 ms	50268 KB	Output is correct
13	Correct	375 ms	50300 KB	Output is correct
14	Correct	384 ms	50300 KB	Output is correct

Subtask #2
45.0 / 45.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	379 ms	49784 KB	Output is correct
2	Correct	364 ms	49840 KB	Output is correct
3	Correct	371 ms	49840 KB	Output is correct
4	Correct	384 ms	49960 KB	Output is correct
5	Correct	362 ms	50012 KB	Output is correct
6	Correct	358 ms	50212 KB	Output is correct
7	Correct	368 ms	50212 KB	Output is correct
8	Correct	370 ms	50212 KB	Output is correct
9	Correct	382 ms	50260 KB	Output is correct
10	Correct	374 ms	50260 KB	Output is correct
11	Correct	369 ms	50268 KB	Output is correct
12	Correct	367 ms	50268 KB	Output is correct
13	Correct	375 ms	50300 KB	Output is correct
14	Correct	384 ms	50300 KB	Output is correct
15	Correct	374 ms	50460 KB	Output is correct
16	Correct	379 ms	51868 KB	Output is correct
17	Correct	387 ms	52344 KB	Output is correct
18	Correct	393 ms	52488 KB	Output is correct
19	Correct	392 ms	52900 KB	Output is correct
20	Correct	398 ms	52900 KB	Output is correct
21	Correct	406 ms	53444 KB	Output is correct
22	Correct	387 ms	53832 KB	Output is correct
23	Correct	393 ms	54216 KB	Output is correct
24	Correct	381 ms	54476 KB	Output is correct
25	Correct	399 ms	54984 KB	Output is correct
26	Correct	385 ms	55480 KB	Output is correct
27	Correct	379 ms	55716 KB	Output is correct
28	Correct	419 ms	56204 KB	Output is correct

Subtask #3
40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	379 ms	49784 KB	Output is correct
2	Correct	364 ms	49840 KB	Output is correct
3	Correct	371 ms	49840 KB	Output is correct
4	Correct	384 ms	49960 KB	Output is correct
5	Correct	362 ms	50012 KB	Output is correct
6	Correct	358 ms	50212 KB	Output is correct
7	Correct	368 ms	50212 KB	Output is correct
8	Correct	370 ms	50212 KB	Output is correct
9	Correct	382 ms	50260 KB	Output is correct
10	Correct	374 ms	50260 KB	Output is correct
11	Correct	369 ms	50268 KB	Output is correct
12	Correct	367 ms	50268 KB	Output is correct
13	Correct	375 ms	50300 KB	Output is correct
14	Correct	384 ms	50300 KB	Output is correct
15	Correct	374 ms	50460 KB	Output is correct
16	Correct	379 ms	51868 KB	Output is correct
17	Correct	387 ms	52344 KB	Output is correct
18	Correct	393 ms	52488 KB	Output is correct
19	Correct	392 ms	52900 KB	Output is correct
20	Correct	398 ms	52900 KB	Output is correct
21	Correct	406 ms	53444 KB	Output is correct
22	Correct	387 ms	53832 KB	Output is correct
23	Correct	393 ms	54216 KB	Output is correct
24	Correct	381 ms	54476 KB	Output is correct
25	Correct	399 ms	54984 KB	Output is correct
26	Correct	385 ms	55480 KB	Output is correct
27	Correct	379 ms	55716 KB	Output is correct
28	Correct	419 ms	56204 KB	Output is correct
29	Correct	2393 ms	136476 KB	Output is correct
30	Correct	2542 ms	157884 KB	Output is correct
31	Correct	3173 ms	184352 KB	Output is correct
32	Correct	2192 ms	207480 KB	Output is correct
33	Correct	1751 ms	219720 KB	Output is correct
34	Correct	2633 ms	250852 KB	Output is correct
35	Correct	2939 ms	289636 KB	Output is correct
36	Correct	2821 ms	289636 KB	Output is correct
37	Correct	3964 ms	289636 KB	Output is correct

Submission #50711

Compilation message

Subtask #1 15.0 / 15.0

Subtask #2 45.0 / 45.0

Subtask #3 40.0 / 40.0

Subtask #1
15.0 / 15.0

Subtask #2
45.0 / 45.0

Subtask #3
40.0 / 40.0