Submission #547888

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
547888	2022-04-12T01:13:11 Z	racsosabe	Hyper-minimum (IZhO11_hyper)	C++14	0 / 100	947 ms	95948 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 <= m; d++, dis <<= 1){
		assert(d < 8);
		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++){
						vector<int> pos = {i, j, k, 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:66:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
hyper.cpp:71:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |      scanf("%d", &a[i][j][k][l]);
      |      ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1

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	8 ms	2132 KB	Output is correct
4	Correct	7 ms	2132 KB	Output is correct
5	Correct	6 ms	2260 KB	Output is correct
6	Correct	31 ms	6000 KB	Output is correct
7	Correct	36 ms	5892 KB	Output is correct
8	Correct	132 ms	12364 KB	Output is correct
9	Correct	68 ms	14048 KB	Output is correct
10	Correct	111 ms	12680 KB	Output is correct
11	Correct	267 ms	23436 KB	Output is correct
12	Correct	535 ms	38852 KB	Output is correct
13	Correct	645 ms	37752 KB	Output is correct
14	Correct	519 ms	43620 KB	Output is correct
15	Correct	622 ms	59100 KB	Output is correct
16	Runtime error	947 ms	95948 KB	Execution killed with signal 11
17	Halted	0 ms	0 KB	-