답안 #41017 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
41017	2018-02-11T17:59:07 Z	IvanC	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	2262 ms	19700 KB

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

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.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	356 KB	Output is correct
3	Correct	2 ms	540 KB	Output is correct
4	Correct	2 ms	540 KB	Output is correct
5	Correct	2 ms	540 KB	Output is correct
6	Correct	1 ms	540 KB	Output is correct
7	Correct	2 ms	540 KB	Output is correct
8	Correct	2 ms	540 KB	Output is correct
9	Correct	2 ms	540 KB	Output is correct
10	Correct	2 ms	592 KB	Output is correct
11	Correct	2 ms	596 KB	Output is correct
12	Correct	2 ms	600 KB	Output is correct
13	Correct	1 ms	604 KB	Output is correct
14	Correct	2 ms	604 KB	Output is correct

Subtask #2
45.0 / 45.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	356 KB	Output is correct
3	Correct	2 ms	540 KB	Output is correct
4	Correct	2 ms	540 KB	Output is correct
5	Correct	2 ms	540 KB	Output is correct
6	Correct	1 ms	540 KB	Output is correct
7	Correct	2 ms	540 KB	Output is correct
8	Correct	2 ms	540 KB	Output is correct
9	Correct	2 ms	540 KB	Output is correct
10	Correct	2 ms	592 KB	Output is correct
11	Correct	2 ms	596 KB	Output is correct
12	Correct	2 ms	600 KB	Output is correct
13	Correct	1 ms	604 KB	Output is correct
14	Correct	2 ms	604 KB	Output is correct
15	Correct	2 ms	616 KB	Output is correct
16	Correct	7 ms	1516 KB	Output is correct
17	Correct	14 ms	1848 KB	Output is correct
18	Correct	14 ms	2120 KB	Output is correct
19	Correct	12 ms	2436 KB	Output is correct
20	Correct	12 ms	2580 KB	Output is correct
21	Correct	20 ms	3080 KB	Output is correct
22	Correct	15 ms	3464 KB	Output is correct
23	Correct	15 ms	3864 KB	Output is correct
24	Correct	15 ms	4124 KB	Output is correct
25	Correct	16 ms	4724 KB	Output is correct
26	Correct	16 ms	4724 KB	Output is correct
27	Correct	20 ms	4724 KB	Output is correct
28	Correct	26 ms	4724 KB	Output is correct

Subtask #3
40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	356 KB	Output is correct
3	Correct	2 ms	540 KB	Output is correct
4	Correct	2 ms	540 KB	Output is correct
5	Correct	2 ms	540 KB	Output is correct
6	Correct	1 ms	540 KB	Output is correct
7	Correct	2 ms	540 KB	Output is correct
8	Correct	2 ms	540 KB	Output is correct
9	Correct	2 ms	540 KB	Output is correct
10	Correct	2 ms	592 KB	Output is correct
11	Correct	2 ms	596 KB	Output is correct
12	Correct	2 ms	600 KB	Output is correct
13	Correct	1 ms	604 KB	Output is correct
14	Correct	2 ms	604 KB	Output is correct
15	Correct	2 ms	616 KB	Output is correct
16	Correct	7 ms	1516 KB	Output is correct
17	Correct	14 ms	1848 KB	Output is correct
18	Correct	14 ms	2120 KB	Output is correct
19	Correct	12 ms	2436 KB	Output is correct
20	Correct	12 ms	2580 KB	Output is correct
21	Correct	20 ms	3080 KB	Output is correct
22	Correct	15 ms	3464 KB	Output is correct
23	Correct	15 ms	3864 KB	Output is correct
24	Correct	15 ms	4124 KB	Output is correct
25	Correct	16 ms	4724 KB	Output is correct
26	Correct	16 ms	4724 KB	Output is correct
27	Correct	20 ms	4724 KB	Output is correct
28	Correct	26 ms	4724 KB	Output is correct
29	Correct	1376 ms	18712 KB	Output is correct
30	Correct	1393 ms	19628 KB	Output is correct
31	Correct	1528 ms	19656 KB	Output is correct
32	Correct	1620 ms	19700 KB	Output is correct
33	Correct	1103 ms	19700 KB	Output is correct
34	Correct	1480 ms	19700 KB	Output is correct
35	Correct	2262 ms	19700 KB	Output is correct
36	Correct	1650 ms	19700 KB	Output is correct
37	Correct	2187 ms	19700 KB	Output is correct

답안 #41017

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