Submission #547890

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
547890	2022-04-12T01:17:15 Z	racsosabe	Hyper-minimum (IZhO11_hyper)	C++14	100 / 100	1008 ms	66228 KB

hyper

#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]);
      |      ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	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