Submission #547883

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
547883	2022-04-12T01:06:54 Z	racsosabe	Hyper-minimum (IZhO11_hyper)	C++14	0 / 100	1458 ms	135628 KB

hyper

#include<bits/stdc++.h>
using namespace::std;

const int N = 40;
const int LOG = 8;

int n;
int m;
int len;
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 i, int j, int k, int l, int dis, int pot){
	int ans = INT_MAX;
	vector<int> pos = {i, j, k, l};
	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;
		}
		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();
	int pot = 0;
	int 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++){
					printf("%d%c", query(i, j, k, l, dis, pot), " \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:63:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
hyper.cpp:68:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |      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	9 ms	2516 KB	Output is correct
4	Correct	6 ms	2516 KB	Output is correct
5	Correct	5 ms	2516 KB	Output is correct
6	Correct	33 ms	6736 KB	Output is correct
7	Correct	41 ms	6684 KB	Output is correct
8	Correct	152 ms	14100 KB	Output is correct
9	Correct	69 ms	15760 KB	Output is correct
10	Correct	112 ms	14156 KB	Output is correct
11	Correct	276 ms	27468 KB	Output is correct
12	Correct	560 ms	45072 KB	Output is correct
13	Correct	692 ms	43920 KB	Output is correct
14	Correct	528 ms	49752 KB	Output is correct
15	Correct	636 ms	69032 KB	Output is correct
16	Correct	983 ms	57400 KB	Output is correct
17	Correct	805 ms	58716 KB	Output is correct
18	Correct	810 ms	80072 KB	Output is correct
19	Correct	1061 ms	69156 KB	Output is correct
20	Runtime error	1458 ms	135628 KB	Execution killed with signal 11
21	Halted	0 ms	0 KB	-