답안 #547890

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
547890 2022-04-12T01:17:15 Z racsosabe 최솟값 배열 (IZhO11_hyper) C++14
100 / 100
1008 ms 66228 KB
#include<bits/stdc++.h>
using namespace::std;

const int N = 35;
const int LOG = 8;

int n;
int m;
int len;
int pot;
int dis;
int pos[5];
int a[N][N][N][N];
int ST[N][N][N][N][LOG];

void init(){
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			for(int k = 0; k < n; k++){
				for(int l = 0; l < n; l++){
					ST[i][j][k][l][0] = a[i][j][k][l];
				}
			}
		}
	}
	for(int d = 1, dis = 1; 2 * dis <= n; d++, dis <<= 1){
		assert(d < 8);
		for(int i = 0; i + 2 * dis - 1 < n; i++){
			for(int j = 0; j + 2 * dis - 1 < n; j++){
				for(int k = 0; k + 2 * dis - 1 < n; k++){
					for(int l = 0; l + 2 * dis - 1 < n; l++){
						pos[0] = i;
						pos[1] = j;
						pos[2] = k;
						pos[3] = l;
						ST[i][j][k][l][d] = INT_MAX;
						for(int mask = 0; mask < 16; mask++){
							for(int at = 0, p = 1; at < 4; at++, p <<= 1){
								if(mask & p) pos[at] += dis;
							}
							ST[i][j][k][l][d] = min(ST[i][j][k][l][d], ST[pos[0]][pos[1]][pos[2]][pos[3]][d - 1]);
							for(int at = 0, p = 1; at < 4; at++, p <<= 1){
								if(mask & p) pos[at] -= dis;
							}
						}
					}
				}
			}
		}
	}
}

int query(){
	int ans = INT_MAX;
	for(int mask = 0; mask < 16; mask++){
		for(int at = 0, p = 1; at < 4; at++, p <<= 1){
			if(mask & p) pos[at] += m - dis;
		}
		if(*max_element(pos, pos + 4) >= n) while(true);
		ans = min(ans, ST[pos[0]][pos[1]][pos[2]][pos[3]][pot]);
		for(int at = 0, p = 1; at < 4; at++, p <<= 1){
			if(mask & p) pos[at] -= m - dis;
		}
	}
	return ans;
}

int main(){
	scanf("%d %d", &n, &m);
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			for(int k = 0; k < n; k++){
				for(int l = 0; l < n; l++){
					scanf("%d", &a[i][j][k][l]);
				}
			}
		}
	}
	init();
	pot = 0;
	dis = 1;
	while((dis << 1) <= m){
		dis <<= 1;
		pot++;
	}
	for(int i = 0; i + m - 1 < n; i++){
		for(int j = 0; j + m - 1 < n; j++){
			for(int k = 0; k + m - 1 < n; k++){
				for(int l = 0; l + m - 1 < n; l++){
					pos[0] = i;
					pos[1] = j;
					pos[2] = k;
					pos[3] = l;
					printf("%d%c", query(), " \n"[i + m == n and j + m == n and k + m == n and l + m == n]);
				}
			}
		}
	}
	return 0;
}

Compilation message

hyper.cpp: In function 'int main()':
hyper.cpp:69:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
hyper.cpp:74:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |      scanf("%d", &a[i][j][k][l]);
      |      ~~~~~^~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 4 ms 2132 KB Output is correct
4 Correct 4 ms 2132 KB Output is correct
5 Correct 5 ms 2232 KB Output is correct
6 Correct 22 ms 5972 KB Output is correct
7 Correct 18 ms 5844 KB Output is correct
8 Correct 64 ms 12388 KB Output is correct
9 Correct 112 ms 14136 KB Output is correct
10 Correct 64 ms 12392 KB Output is correct
11 Correct 171 ms 23552 KB Output is correct
12 Correct 366 ms 38792 KB Output is correct
13 Correct 363 ms 37756 KB Output is correct
14 Correct 510 ms 43576 KB Output is correct
15 Correct 821 ms 59024 KB Output is correct
16 Correct 514 ms 47440 KB Output is correct
17 Correct 544 ms 48784 KB Output is correct
18 Correct 1008 ms 66228 KB Output is correct
19 Correct 728 ms 55204 KB Output is correct
20 Correct 673 ms 53132 KB Output is correct