Submission #41017

#	Time	Username	Problem	Language	Result	Execution time	Memory
41017		IvanC	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	2262 ms	19700 KiB

joioi

#include <bits/stdc++.h>
#pragma GCC optimize ("unroll-loops")
using namespace std;
const int MAXN = 2010;
int matriz[MAXN][MAXN],MinVal,MaxVal,N,M,satisfazem;
void flip1(){
	for(int linha = 1;linha<=N;linha++){
		for(int i = 1,j = M;i <= j;i++,j--){
			swap(matriz[linha][i],matriz[linha][j]);
		}
	}
}
void flip2(){
	for(int coluna = 1;coluna<=M;coluna++){
		for(int i = 1,j = N;i<=j;i++,j--){
			swap(matriz[i][coluna],matriz[j][coluna]);
		}
	}
}
int checa1(int delta){
	int last = M;
	int tot = 0;
	for(int linha = 1;linha<=N;linha++){
		int old = last;
		last = 0;
		for(int coluna = 1;coluna<=old;coluna++){
			if(matriz[linha][coluna] > MinVal + delta) break;
			if(matriz[linha][coluna] < MaxVal - delta) tot++;
			last = coluna;
		}
	}
	return tot;
}
int checa2(int delta){
	int last = N;
	int tot = 0;
	for(int coluna = 1;coluna<=M;coluna++){
		int old = last;
		last = 0;
		for(int linha = 1;linha<=old;linha++){
			if(matriz[linha][coluna] > MinVal + delta) break;
			if(matriz[linha][coluna] < MaxVal - delta) tot++;
			last = linha;
		}
	}
	return tot;
}
int checa(int delta){
	satisfazem = 0;
	for(int i = 1;i<=N;i++){
		for(int j = 1;j<=M;j++){
			if(matriz[i][j] < MaxVal - delta) satisfazem++;
		}
	}
	if(checa1(delta) == satisfazem) return 1;
	flip1();
	if(checa1(delta) == satisfazem) return 1;
	flip2();
	if(checa1(delta) == satisfazem) return 1;
	flip1();
	if(checa1(delta) == satisfazem) return 1;
	if(checa2(delta) == satisfazem) return 1;
	flip1();
	if(checa2(delta) == satisfazem) return 1;
	flip2();
	if(checa2(delta) == satisfazem) return 1;
	flip1();
	if(checa2(delta) == satisfazem) return 1;
	return 0;
}
int main(){
	scanf("%d %d",&N,&M);
	for(int i = 1;i<=N;i++){
		for(int j = 1;j<=M;j++){
			scanf("%d",&matriz[i][j]);
		}
	}
	MinVal = MaxVal = matriz[1][1];
	for(int i = 1;i<=N;i++){
		for(int j = 1;j<=M;j++){
			MinVal = min(MinVal,matriz[i][j]);
			MaxVal = max(MaxVal,matriz[i][j]);
		}
	}
	int ini = 0, fim = MaxVal - MinVal,resp = -1,meio;
	while(ini <= fim){
		meio = (ini+fim)/2;
		if(checa(meio)){
			resp = meio;
			fim = meio - 1;
		}
		else{
			ini = meio + 1;
		}
	}
	printf("%d\n",resp);
	return 0;
}

Compilation message (stderr)

joioi.cpp: In function 'int main()':
joioi.cpp:72:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&N,&M);
                      ^
joioi.cpp:75:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&matriz[i][j]);
                             ^

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